#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EPS 1e-10
#define set0(x) memset((x),0,sizeof(x))
#define setINF(x) memset((x),63,sizeof(x))
/*
	Problem: How to Create a Good Game
	Source: AOJ 2230
	Author: fts2001 (the_silliest)
 */
using namespace std;
const int N=205;
typedef int T;
struct edge{
    int to,rev;
    T cap,cost;
};
edge make_edge(int to,T cap,T cost,int rev){
    edge tmp;
    tmp.to=to;
    tmp.cap=cap;
    tmp.cost=cost;
    tmp.rev=rev;
    return tmp;
}
vector<edge> g[N];
void add_edge(int u,int v,T cap,T cost){
    g[u].push_back(make_edge(v,cap,cost,(int)g[v].size()));
    g[v].push_back(make_edge(u,0,-cost,(int)g[u].size()-1));
}
int v,s,t,prevv[N],preve[N];
T h[N],dist[N];
T min_cost_flow(T f){
    T res=0;
    fill(h,h+v,0);
    while(f>0){
        priority_queue<pair<T,int> > pq;
        fill(dist,dist+v,INF);
        dist[s]=0;
        pq.push(make_pair(0,s));
        while(!pq.empty()){
            T cost=-pq.top().first;
            int u=pq.top().second;
            pq.pop();
            if(dist[u]<cost)continue;
            for(int i=0;i<g[u].size();i++){
                edge &ed=g[u][i];
                if(ed.cap>0 && dist[ed.to]>dist[u]+ed.cost+h[u]-h[ed.to]){
                    dist[ed.to]=dist[u]+ed.cost+h[u]-h[ed.to];
                    prevv[ed.to]=u;
                    preve[ed.to]=i;
                    pq.push(make_pair(-dist[ed.to],ed.to));
                }
            }
        }
        if(dist[t]==INF)return -1;
        for(int i=0;i<v;i++){
            h[i]+=dist[i];
        }
        T d=f;
        for(int i=t;i!=s;i=prevv[i]){
            d=min(d,g[prevv[i]][preve[i]].cap);
        }
        f-=d;
        res+=d*h[t];
        for(int i=t;i!=s;i=prevv[i]){
            edge &ed=g[prevv[i]][preve[i]];
            ed.cap-=d;
            g[ed.to][ed.rev].cap+=d;
        }
    }
    return res;
}
int n,m,in[N],out[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    s=n;
    t=n+1;
    v=n+2;
    int sum=0;
    for(int i=0;i<m;i++){
        int u,v,c;
        cin>>u>>v>>c;
        add_edge(u,v,INF,-c);
        sum+=c;
        in[v]++;
        out[u]++;
    }
    int deg=0;
    for(int i=0;i<n;i++){
        if(in[i]>out[i])deg+=in[i]-out[i];
    }
    setINF(dist);
    priority_queue<pair<T,int> > pq;
    fill(dist,dist+v,INF);
    dist[0]=0;
    pq.push(make_pair(0,0));
    while(!pq.empty()){
        T cost=-pq.top().first;
        int u=pq.top().second;
        pq.pop();
        if(dist[u]<cost)continue;
        for(int i=0;i<g[u].size();i++){
            edge &ed=g[u][i];
            if(ed.cap>0 && dist[ed.to]>dist[u]+ed.cost){
                dist[ed.to]=dist[u]+ed.cost;
                pq.push(make_pair(-dist[ed.to],ed.to));
            }
        }
    }
    add_edge(n-1,0,INF,-dist[n-1]);
    for(int i=0;i<n;i++){
        if(in[i]>out[i])add_edge(s,i,in[i]-out[i],0);
        else add_edge(i,t,out[i]-in[i],0);
    }
    cout<<min_cost_flow(deg)-sum<<endl;
    return 0;
}

Measured memory_bytes: 3268