#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define add(a,b,c) (e[i]=b,pre[i]=last[a],last[a]=i,w[i]=c)
#define prec 1e-6
#define inf 1e9
using namespace std;
struct edge
{    int u,v,w;
   edge(int u=0,int v=0,int w=0):u(u),v(v),w(w) {}
};
struct simplex
{    double v;
   double a[1205][1205];
   double b[1205];
   double c[1205];
   int basic[1205];
   int nbasic[105];
   void pivot(int l,int e);
   double opt();
   void output();
};
int fcmp(double x)
{    if (fabs(x)<prec)
       return 0;
   return x>0?1:-1;
}
edge ed[1005];
int last[1005];
int pre[2005];
int deg[105];
int e[2005];
int w[2005];
int f[105];
int n,m;
simplex lp;
void simplex::output()
{    int i,j;
   for (i=1;i<=m;++i)
   {    printf("x[%d]=%.2f-",basic[i],b[basic[i]]);
       for (j=1;j<=n;++j)
           printf("%c%.2fx[%d]",j==1?'(':'+',a[basic[i]][nbasic[j]],nbasic[j]);
       printf(")\n");
   }
   printf("maximize ");
   printf("%.2f",v);
   for (i=1;i<=n;++i)
       printf("+%.2fx[%d]",c[nbasic[i]],nbasic[i]);
   printf("\n\n");
}
void simplex::pivot(int l,int e)
{    static double ta[1205][1205];
   static double tb[1205];
   static double tc[1205];
   int i,j;
   memset(ta,0,sizeof(ta));
   memset(tb,0,sizeof(tb));
   memset(tc,0,sizeof(tc));
   tb[e]=b[l]/a[l][e];
   ta[e][l]=1.0/a[l][e];
   for (i=1;i<=n;++i)
       if (nbasic[i]!=e)
           ta[e][nbasic[i]]=a[l][nbasic[i]]/a[l][e];
   for (i=1;i<=m;++i)
   {    tb[basic[i]]=b[basic[i]]-a[basic[i]][e]*tb[e];
       ta[basic[i]][l]=-a[basic[i]][e]*ta[e][l];
       for (j=1;j<=n;++j)
           if (nbasic[j]!=e)
               ta[basic[i]][nbasic[j]]=a[basic[i]][nbasic[j]]-a[basic[i]][e]*ta[e][nbasic[j]];
   }
   v=v+tb[e]*c[e];
   tc[l]=-ta[e][l]*c[e];
   for (i=1;i<=n;++i)
       if (nbasic[i]!=e)
           tc[nbasic[i]]=c[nbasic[i]]-c[e]*ta[e][nbasic[i]];
   for (i=1;i<=n;++i)
       if (nbasic[i]==e)
           nbasic[i]=l;
   for (i=1;i<=m;++i)
       if (basic[i]==l)
           basic[i]=e;
   for (i=1;i<=m;++i)
   {    for (j=1;j<=n;++j)
           a[basic[i]][nbasic[j]]=ta[basic[i]][nbasic[j]];
       b[basic[i]]=tb[basic[i]];
   }
   for (i=1;i<=n;++i)
       c[nbasic[i]]=tc[nbasic[i]];
}
double simplex::opt()
{    double delta;
   int i,l,e;
   while (1)
   {    e=n+m+2;
       for (i=1;i<=n;++i)
           if (fcmp(c[nbasic[i]])>0&&nbasic[i]<e)
               e=nbasic[i];
       if (e==n+m+2)
           return v;
       delta=-1;
       l=n+m+2;
       for (i=1;i<=m;++i)
           if (fcmp(a[basic[i]][e])>0)
           {    double t=b[basic[i]]/a[basic[i]][e];
               if (l==n+m+2||fcmp(t-delta)<0||(fcmp(t-delta)==0&&basic[i]<l))
               {    delta=t;
                   l=basic[i];
               }
           }
       if (l==n+m+2)
           return inf;
       else pivot(l,e);
   }
}
int longest_path()
{    int q[105];
   int i,h,t;
   q[h=t=1]=1;
   while (h<=t)
   {    for (i=last[q[h]];i!=0;i=pre[i])
       {    f[e[i]]=max(f[e[i]],f[q[h]]+w[i]);
           --deg[e[i]];
           if (deg[e[i]]==0)
               q[++t]=e[i];
       }
       ++h;
   }
   return f[n];
}
void buildlp()
{    int i,j;
   for (i=1;i<=n;++i)
       lp.nbasic[i]=i;
   for (i=1;i<=m;++i)
   {    ++lp.c[ed[i].v];
       --lp.c[ed[i].u];
       lp.v+=f[ed[i].v]-f[ed[i].u]-ed[i].w;
   }
   for (i=1;i<=m;++i)
   {    lp.a[n+i][ed[i].v]=-1;
       lp.a[n+i][ed[i].u]=1;
       lp.b[n+i]=f[ed[i].v]-f[ed[i].u]-ed[i].w;
       lp.basic[i]=n+i;
   }
   for (i=1;i<n;++i)
   {    lp.a[n+m+i][i]=-1;
       lp.basic[m+i]=n+m+i;
   }
   lp.a[n+m+n][n]=1;
   lp.basic[m+n]=n+m+n;
   m+=n;
}
int main()
{    int i,a,b,c;
   scanf("%d%d",&n,&m);
   for (i=1;i<=m;++i)
   {    scanf("%d%d%d",&a,&b,&c);
       ++a,++b;
       ++deg[b];
       ed[i]=edge(a,b,c);
       add(a,b,c);
   }
   longest_path();
   buildlp();
   printf("%d\n",(int)lp.opt());
   fclose(stdin);
   fclose(stdout);
   return 0;
}
//蛻?梵?喇ttp://blog.sina.com.cn/s/blog_4a0c4e5d0101glxu.html

Measured memory_bytes: 23276