#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;

using _loop_int = int;
#define REP(i,n) for(_loop_int i=0; i<(_loop_int)(n); i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a); i<(_loop_int)(b); i++)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1; i>=(_loop_int)(a); i--)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))
#define ALL(v) (v).begin(),(v).end()

#define DEBUG(x) cerr<<#x<<": "<<(x)<<endl
#define DEBUG_VEC(v) cerr<<#v<<": ";REP(__i,(v).size())cerr<<((v)[__i])<<", ";cerr<<endl

const ll MOD = 1000000007ll;

template<typename T>
struct MCF {
    using P = pair<T,int>;
    struct edge {
        int to; T cap; T cost; int rev;
        edge(int a, T b, T c, int d):to(a),cap(b),cost(c),rev(d){}
    };
    vector<vector<edge>> G;
    vector<T> h,dist;
    vector<int> prevv,preve;
    int V;
    MCF(int v):G(v),prevv(v,0),preve(v,0),V(v){}
    void add_edge(int from, int to, T cap, T cost){
        G[from].push_back(edge(to,cap,cost,G[to].size()));
        G[to].push_back(edge(from,0,-cost,G[from].size()-1));
    }
    T solve(int s, int t, T f, T COST_INF=(1<<30)){
        T res = 0;
        h.assign(V, 0);
        while(f > 0){
            priority_queue<P,vector<P>,greater<P>> Q;
            dist.assign(V, COST_INF);
            dist[s] = 0;
            Q.push(P(0,s));
            while(Q.size()){
                P p = Q.top(); Q.pop();
                int v = p.second;
                if(dist[v] < p.first)continue;
                REP(i,G[v].size()){
                    edge &e = G[v][i];
                    T d = dist[v] + e.cost + h[v] - h[e.to];
                    if(e.cap > 0 && dist[e.to] > d){
                        dist[e.to] = d;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        Q.push(P(dist[e.to], e.to));
                    }
                }
            }
            if(dist[t] == COST_INF){
                // return -1;
                break;
            }
            REP(v,V)h[v] += dist[v];
            T d = f;
            for(int v=t; v!=s; v=prevv[v]){
                d = min(d, G[prevv[v]][preve[v]].cap);
            }
            f -= d;
            res += d*h[t];
            for(int v=t; v!=s; v=prevv[v]){
                edge &e = G[prevv[v]][preve[v]];
                e.cap -= d;
                G[v][e.rev].cap += d;
            }
        }
        return res;
    }
};

template<typename T>
struct MCC {
    MCF<T> mcf;
    int V,source,sink;
    T sum;
    MCC(int v):V(v+2),mcf(v+2),source(v),sink(v+1),sum(0){}
    void add_edge(int from, int to, T lb, T ub, T cost){
        if(cost < 0){
            sum += cost * ub;
            mcf.add_edge(source,to,ub,0);
            mcf.add_edge(from,sink,ub,0);
            if(ub-lb > 0){
                mcf.add_edge(to,from,ub-lb,-cost);
            }
        }else{
            sum += cost * lb;
            if(lb > 0){
                mcf.add_edge(source,to,lb,0);
                mcf.add_edge(from,sink,lb,0);
            }
            if(ub-lb > 0){
                mcf.add_edge(from,to,ub-lb,cost);
            }
        }
    }
    T solve(T f, T COST_INF=(1<<30)){
        return sum + mcf.solve(source, sink, f, COST_INF);
    }
};

int n,m;
vector<pii> g[125];

int main(){
    scanf("%d%d",&n,&m);
    REP(i,m){
        int x,y,s;
        scanf("%d%d%d",&x,&y,&s);
        g[x].push_back(pii(y,s));
    }
    // calc max dist (DAG)
    vector<int> dist(n, 0);
    REP(i,n)for(pii P : g[i])CHMAX(dist[P.first], dist[i]+P.second);
    int x = dist[n-1];
    const ll INF = 1ll<<30;
    MCC<ll> mcc(n);
    const int start = 0;
    const int goal = n-1;
    // constraint: goal - start <= x
    // > goal - start <= x -> cost = 0
    // > goal - start >  x -> cost = INF
    mcc.add_edge(start, goal, 0, INF, x);
    REP(u,n)for(pii P : g[u]){
        int v = P.first;
        int s = P.second;
        // constraint: v - u >= s
        // > u - v <= -s -> cost = 1 * (u - v)
        // > u - v >  -s -> cost = INF
        mcc.add_edge(v, u, 1, INF, -s);
    }
    ll ans = mcc.solve(1ll<<60, 1ll<<60);
    printf("%lld\n",ans);
    return 0;
}



Measured memory_bytes: 3356