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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

struct PrimalDual{
    typedef long long F;
    static const F  INF;
    
    struct Edge{
        int to;
        F cap,cost;
        int rev;
        Edge(int to,F cap,F cost,int rev):to(to),cap(cap),cost(cost),rev(rev){}
    };
    
    int n;
    vector<vector<Edge>>G;

    PrimalDual(int n):n(n),G(n){}

    void addEdge(int from,int to,F cap,F cost){
        G[from].push_back(Edge(to,cap,cost,G[to].size()));
        G[to].push_back(Edge(from,0,-cost,G[from].size()-1));
    }


    F minCostFlow(int s,int t,F f){
        F cur=0;

        vector<F>h(n);
        vector<int>prevv(n,-1),preve(n,-1);
        vector<F>dist(n);
        priority_queue<pair<F,int>,vector<pair<F,int>>,greater<pair<F,int>>>que;
        
        h.assign(n,INF);
        h[s]=0;
        while(true){
            bool update=false;
            rep(v,n){
                for(auto &e:G[v]){
                    if(e.cap&&h[e.to]>h[v]+e.cost){
                        update=true;
                        h[e.to]=h[v]+e.cost;
                    }
                }
            }
            if(!update)break;
        }

        while(f>0){
            fill(dist.begin(),dist.end(),INF);
            dist[s]=0;
            que.emplace(0,s); 
            while(que.size()){
                F d;
                int v;
                tie(d,v)=que.top();
                que.pop();
                if(dist[v]<d)continue;
                for(int i=0;i<G[v].size();i++){
                    Edge &e=G[v][i];
                    F nd=dist[v]+e.cost+h[v]-h[e.to];
                    if(e.cap>0&&dist[e.to]>nd){
                        dist[e.to]=nd;
                        prevv[e.to]=v;preve[e.to]=i;
                        que.emplace(nd,e.to);
                    }
                }
            }
            if(dist[t]==INF)return -1;
            for(int v=0;v<n;v++)h[v]+=dist[v];
            F nf=f;
            for(int v=t;v!=s;v=prevv[v]){
                nf=min(nf,G[prevv[v]][preve[v]].cap);
            }
            f-=nf;
            cur+=nf*h[t];
            for(int v=t;v!=s;v=prevv[v]){
                Edge &e=G[prevv[v]][preve[v]];
                e.cap-=nf;
                G[v][e.rev].cap+=nf;
            }
        }
        return cur;
    }
};
const PrimalDual::F PrimalDual::INF=1ll<<50;

int N,M;
int X[1111],Y[1111],C[1111];

signed main(){
    scanf("%lld%lld",&N,&M);
    rep(i,M)scanf("%lld%lld%lld",&X[i],&Y[i],&C[i]);

    vector<vector<pint>>G(N);
    rep(i,M){
        G[X[i]].emplace_back(Y[i],C[i]);
    }
    vint dist(N,-1001001001);
    dist[0]=0;
    rep(v,N){
        for(auto &e:G[v]){
            chmax(dist[e.fi],dist[v]+e.se);
        }   
    }
    int D=dist[N-1];

    PrimalDual pd(N+2);
    int src=N,dst=N+1;
    vector<int>d(N);
    int ans=0;
    rep(i,M){
        pd.addEdge(X[i],Y[i],PrimalDual::INF,-C[i]);
        ans-=C[i];
        d[X[i]]--;
        d[Y[i]]++;
    }
    pd.addEdge(N-1,0,PrimalDual::INF,D);
    int f=0;
    rep(i,N){
        if(d[i]<0){
            pd.addEdge(i,dst,-d[i],0);
        }
        else if(d[i]>0){
            f+=d[i];
            pd.addEdge(src,i,d[i],0);
        }
    }

    ans+=pd.minCostFlow(src,dst,f);
    printf("%lld\n",ans);
    return 0;
}



Measured memory_bytes: 3384