#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;

#define MAXN 1110
#define MAXM 1110
#define INF 1E200

double A[MAXM+5][MAXN+MAXM+5];
double b[MAXM+5],c[MAXN+MAXM+5];
int N[MAXN+5],B[MAXM+5];
double X[MAXN+MAXM+5],V;
int n,m,R,C,nCnt,bCnt;
int v1[MAXN],v2[MAXN];

int fcmp(double a,double b)
{
    if (fabs(a-b)<1E-7) return 0;
    if (a>b) return 1;
    return -1;
}

void Pivot(int l,int e)
{
    double t=A[l][e],p=c[e];
    b[l]=b[l]/t;
    for (int i=1;i<=C;i++)
        A[l][i]/=t;
    V=V-c[e]*b[l];
    for (int i=1;i<=R;i++)
    {
        if (i==l||fcmp(A[i][e],0.0)==0)
            continue;
        t=A[i][e];
        b[i]=b[i]-t*b[l];
        for (int j=1;j<=C;j++)
            A[i][j]=A[i][j]-t*A[l][j];
    }
    for (int i=1;i<=C;i++)
        c[i]=c[i]-p*A[l][i];
    for (int i=1;i<=nCnt;i++)
    {
        if (N[i]==e)
        {
            N[i]=B[l];
            break;
        }
    }
    B[l]=e;
}

bool Process(double P[])
{
    while (true)
    {
        int e=-1;
        double mV=-INF;
        for (int i=1;i<=nCnt;i++)
            if (fcmp(P[N[i]],mV)==1)
                mV=P[N[i]],e=N[i];

        if (fcmp(mV,0.0)<=0) break;
        int l=-1;
        mV=INF;
        for (int i=1;i<=bCnt;i++)
        {
            if (fcmp(A[i][e],0.0)==1)
            {
                double t=b[i]/A[i][e];
                if (fcmp(mV,t)==1||(fcmp(mV,t)==0&&(l==-1||B[l]>B[i])))
                    mV=t,l=i;
            }
        }
        if (l==-1) return false;
        Pivot(l,e);
    }
    return true;
}

bool initSimplex()
{
    nCnt=bCnt=0;
    for (int i=1;i<=n;i++)
        N[++nCnt]=i;
    for (int i=1;i<=m;i++)
        B[++bCnt]=i+n,A[i][n+i]=1.0;
    R=bCnt,C=bCnt+nCnt;
    double minV=INF;
    int p=-1;
    for (int i=1;i<=m;i++)
        if (fcmp(minV,b[i])==1)
            minV=b[i],p=i;
    if (fcmp(minV,0.0)>=0)
        return true;
    N[++nCnt]=n+m+1; R++,C++;
    for (int i=0;i<=C;i++)
        A[R][i]=0.0;
    for (int i=1;i<=R;i++)
        A[i][n+m+1]=-1.0;
    Pivot(p,n+m+1);
    if (!Process(A[R])) return false;
    if (fcmp(b[R],0.0)!=0)
        return false;
    p=-1;
    for (int i=1;i<=bCnt&&p==-1;i++)
        if (B[i]==n+m+1) p=i;
    if (p!=-1)
    {
        for (int i=1;i<=nCnt;i++)
        {
            if (fcmp(A[p][N[i]],0.0)!=0)
            {
                Pivot(p,N[i]);
                break;
            }
        }
    }
    bool f=false;
    for (int i=1;i<=nCnt;i++)
    {
        if (N[i]==n+m+1) f=true;
        if (f&&i+1<=nCnt)
            N[i]=N[i+1];
    }
    nCnt--;
    R--,C--;
    return true;
}

//
int Simplex()
{
    if (!initSimplex())
        return -1;
    if (!Process(c))
        return 1;
    for (int i=1;i<=nCnt;i++)
        X[N[i]]=0.0;
    for (int i=1;i<=bCnt;i++)
        X[B[i]]=b[i];
    return 0;
}

struct Edge
{
	int to, next, len;
}edge[1000];
int head[100], L;
void init(int n)
{
	memset(head, -1, 4 * n);
	L = 0;
}
void add_edge(int u, int v, int len)
{
	edge[L].to = v;
	edge[L].len = len;
	edge[L].next = head[u];
	head[u] = L ++;
}
int dp[100];
int calc(int u)
{
	if (dp[u] != -1)
		return dp[u];
	dp[u] = 0;
	for (int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].to;
		dp[u] = max(dp[u], calc(v) + edge[i].len);
	}
	return dp[u];
}

int main()
{
    int nn, mm;
	scanf("%d%d", &nn, &mm);
	init(nn);
	double ans1=0.0;
	for (int i = 0; i < mm; ++ i)
	{
		int u, v, len;
		scanf("%d%d%d", &u, &v, &len);
		add_edge(u, v, len);
		ans1+=len;
	}
	memset(dp, -1, 4 * nn - 4);
	dp[nn - 1] = 0;
	calc(0);
	n = nn+mm;
	m = 1;

    for (int i=1;i<=nn;i++)
	{
	    A[m][i]=-1;
        b[m]=-dp[i-1];
        m++;
	}

	A[m][1]=1;
	b[m]=dp[0];
	m++;

	A[m][nn]=1;
	b[m]=dp[nn-1];
	m++;


	for (int i=0;i<nn;i++)
    {
        for (int j=head[i];j!=-1;j=edge[j].next)
        {

            int u=i,v=edge[j].to;
            A[m][v+1]=1;
            A[m][u+1]=-1;
            A[m][j+nn+1]=1;
            b[m]=-edge[j].len;
            m++;

        }
    }
    m--;

    for (int i=nn+1;i<=n;i++)
        c[i]=1;

    Simplex();
    double ans=0;
    for (int i=nn+1;i<=n;i++)
        ans+=X[i];
    printf("%d\n",(int)(ans+1e-8));
	return 0;
}

Measured memory_bytes: 20292