#include<bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

struct edge{
    int to,cap,cost,rev;
    edge(int a,int b,int c,int d):to(a),cap(b),cost(c),rev(d){}
};

const int MAX_V=111;
const int INF=1001001001001001001ll;
vector<edge>G[MAX_V];

void add_edge(int from,int to,int cap,int cost){
    edge e1(to,cap,cost,G[to].size());
    edge e2(from,0,-cost,G[from].size());

    G[from].pb(e1);
    G[to].pb(e2);
}

int h[MAX_V],dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];


int min_cost_flow(int s,int t){
    fill_n(h,MAX_V,INF);
    h[s]=0;
    vint deg(MAX_V);
    rep(i,MAX_V)for(auto &e:G[i])if(e.cap)deg[e.to]++;

    queue<int>que;
    rep(i,MAX_V)if(deg[i]==0)que.push(i);
    while(que.size()){
        int v=que.front();
        que.pop();
        for(auto &e:G[v])if(e.cap){
            chmin(h[e.to],h[v]+e.cost);
            if(--deg[e.to]==0)que.push(e.to);
        }
    }

    int res=0;
    while(true){
        fill_n(dist,MAX_V,INF);
        dist[s]=0;
        priority_queue<pint,vector<pint>,greater<pint>>que;
        que.push({0,s});
        while(que.size()){
            int c,v;
            tie(c,v)=que.top();
            que.pop();
            if(dist[v]>c)continue;
            for(int i=0;i<G[v].size();i++){
                edge &e=G[v][i];
                if(e.cap==0||dist[e.to]<=dist[v]+e.cost+h[v]-h[e.to])continue;
                dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
                prevv[e.to]=v;
                preve[e.to]=i;
                que.push({dist[e.to],e.to});
            }
        }
        if(dist[t]==INF)return res;

        for(int v=0;v<MAX_V;v++)h[v]+=dist[v];
        if(h[t]>=0)return res;
        int d=INF;
        for(int v=t;v!=s;v=prevv[v])chmin(d,G[prevv[v]][preve[v]].cap);
        res+=h[t]*d;

        for(int v=t;v!=s;v=prevv[v]){
            edge &e=G[prevv[v]][preve[v]];
            e.cap-=d;
            G[e.to][e.rev].cap+=d;
        }
    }
}

signed main(){
    int N,M;
    cin>>N>>M;


    vint A(M),B(M),C(M);
    vector<vpint>G(N);
    rep(i,M){
        cin>>A[i]>>B[i]>>C[i];
        G[A[i]].pb({B[i],C[i]});
    }

    vint dist(N);
    vint deg(N);rep(i,N)for(auto &e:G[i])deg[e.fi]++;
    queue<int>que;
    rep(i,N)if(deg[i]==0)que.push(i);
    while(que.size()){
        int v=que.front();
        que.pop();
        for(auto &e:G[v]){
            chmax(dist[e.fi],dist[v]+e.se);
            if(--deg[e.fi]==0)que.push(e.fi);
        }
    }

    int D=dist[N-1];

    int src=MAX_V-2,snk=MAX_V-1;
    rep(i,N){
        add_edge(src,i,INF,D);
        add_edge(i,snk,INF,0);
    }

    const int X=1000000000;
    rep(i,M){
        add_edge(B[i],A[i],1,-X-C[i]);
        add_edge(B[i],A[i],INF,-C[i]);
    }

    cout<<min_cost_flow(src,snk)+X*M<<endl;
    return 0;
}

Measured memory_bytes: 3248