#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bitset>
using namespace std;
#define inf 0x7fffffff
#define finf (1./0.)
#define eps 1e-8
#define ll long long
#define ld long double
#define pii pair<int,int>
#define x first
#define y second
#define sf scanf
#define pf printf
#define vec vector
#define pb push_back
#define mp make_pair
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define clr(a,b) memset(a,b,sizeof(a))
#define bin_cnt(x) __builtin_popcount(x)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define srep(sub,s) for(int sub=s&(s-1);sub;sub=(sub-1)&s)
#define irep(i,a) for(__typeof(a.begin()) i=a.begin();i!=a.end();i++)
#define irrep(i,a) for(__typeof(a.rbegin()) i=a.rbegin();i!=a.rend();i++)
#pragma GCC optimize ("O2")
#define o2 __attribute__((optimize("O2")))
#pragma comment(linker, "/STACK:32505856")

template<class T> inline T sqr(T a) {return a*a;}
template<class T> inline void gmin(T&a,T b) {if(a>b)a=b;}
template<class T> inline void gmax(T&a,T b) {if(a<b)a=b;}
inline int dcmp(const double &a) {return a>eps?1:(a<-eps?-1:0);}
struct Initializer{Initializer(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}}initializer;

struct LPSolver {
  #define N 110
  #define M 1212
  #define A(e,v) sol.a[e][v-1]
  #define B(e) sol.a[e][sol.n]
  #define C(v) sol.a[0][v-1]
  int n,m;
  double a[M+1][N+1],x[N];
  int basis[M+1],out[N+1];

  void init(int v,int e) {
    n=v,m=e;
    rep(i,0,m) fill(a[i],a[i]+n+1,0);
  }

  void pivot(int p,int q) {
    rep(i,0,m) if (i!=p&&dcmp(a[i][q]))
    rep(j,0,n) if (j!=q) a[i][j]-=a[p][j]*a[i][q]/a[p][q];
    rep(j,0,n) if (j!=q) a[p][j]/=a[p][q];
    rep(i,0,m) if (i!=p) a[i][q]/=-a[p][q];
    a[p][q]=1/a[p][q];
    swap(basis[p],out[q]);
  }

  double simplex() {
    rep(j,0,n-1) a[0][j]=-a[0][j];
    rep(i,0,m) basis[i]=-i;
    rep(j,0,n) out[j]=j;
    while (1) {
      int p=1,q=0;
      rep(i,1,m) if (mp(a[i][n],basis[i])<mp(a[p][n],basis[p])) p=i;
      if (a[p][n]>=0) break;
      rep(j,0,n-1) if (a[p][j]<a[p][q]) q=j;
      if (a[p][q]>=0) return -finf;
      pivot(p,q);
    }
    while (1) {
      int p=1,q=0;
      rep(j,0,n-1) if (mp(a[0][j],out[j])<mp(a[0][q],out[q])) q=j;
      if (a[0][q]>=0) break;
      rep(i,1,m)
        if (a[i][q]>0)
          if (a[p][q]<=0||mp(a[i][n]/a[i][q],basis[i])<mp(a[p][n]/a[p][q],basis[p]))
            p=i;
      if (a[p][q]<=0) return +finf;
      pivot(p,q);
    }
    rep(j,0,n-1) x[j]=0;
    rep(i,1,m) if (basis[i]>=0) x[basis[i]]=a[i][n];
    return a[0][n];
  }
} sol;


ll dist[N][N],sum;

int main() {
//  freopen("in","r",stdin);
  int n,m,l=0;
  sf("%d%d",&n,&m);
  sol.init(n,m+n+n);
  clr(dist,0xf0);

  rep(i,1,m) {
    int u,v,w;
    sf("%d%d%d",&u,&v,&w);
    u++,v++;
    dist[u][v]=w;
    sum+=w;

    l++;
    A(l,u)=1;  //dv>=du+w
    A(l,v)=-1;
    B(l)=-w;

    C(u)--;
    C(v)++;
  }
  rep(i,1,n-1) {
    l++;
    A(l,n)=-1;  //di<=dt
    A(l,i)=1;
  }

  rep(k,1,n)
    rep(i,1,n) if (i!=k)
      rep(j,1,n) if (i!=j && j!=k)
        gmax(dist[i][j],dist[i][k]+dist[k][j]);

  rep(i,1,n) {
    l++;
    A(l,i)=1;
    B(l)=dist[1][n];
  }

  pf("%.0f\n",sol.simplex()+eps-sum);
//  rep(i,0,n-1) pf("X%d=%.0f\n",i+1,sol.x[i]);
  return 0;
}

Measured memory_bytes: 2396