// Slower C++ solution:
#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

// Faster C++ solution for the same problem (measured speedup: 12.452035538418777x):
#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#include<map>

#include<queue>

#include<stack>

#include<vector>

#include<bitset>

#include <functional>

using namespace std;

#define MAX_V 100 + 2

int indegree[MAX_V], outdegree[MAX_V];

int n, m, s, t;

#define INF 0x3f3f3f3f

///////////////////////////////最小?用流?始///////////////////////////////////////////



typedef pair<int, int> P;	// first保存最短距?，second保存?点?号

//用于表示?的??体

struct edge

{

	int to;		// ?点

	int cap;	// 容量

	int cost;	// ?用

	int rev;	// 反向?

	edge(int to, int cap, int cost, int rev) :to(to), cap(cap), cost(cost), rev(rev){}

};

int V;			// ?点数

vector<edge> G[MAX_V];	// ?的?接表

int h[MAX_V];	// ?点的?

int dist[MAX_V];// 最短距?

int prevv[MAX_V];	// 最短路中的前??点

int preve[MAX_V];	// 最短路中的前??点??的?



// 向?中?加一条从from到to的容量?cap?用?cost的?

void add_edge(int from, int to, int cap, int cost)

{

	G[from].push_back(edge(to, cap, cost, G[to].size()));

	G[to].push_back(edge(from, 0, -cost, G[from].size() - 1));

}



// 求解从s到t流量?f的最小?用流，如果没有流量?f的流，?返回-1

int min_cost_flow(int s, int t, int f)

{

	int res = 0;

	memset(h, 0, sizeof(h));

	while (f > 0)

	{

		// 使用Dijkstra算法更新h

		priority_queue<P, vector<P>, greater<P> > que;

		memset(dist, INF, sizeof(dist));

		dist[s] = 0;

		que.push(P(0, s));

		while (!que.empty())

		{

			P p = que.top(); que.pop();

			int v = p.second;

			if (dist[v] < p.first) continue;

			for (int i = 0; i < G[v].size(); ++i)

			{

				edge &e = G[v][i];

				if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to])

				{

					dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];

					prevv[e.to] = v;

					preve[e.to] = i;

					que.push(P(dist[e.to], e.to));

				}

			}

		}

		if (dist[t] == INF)

		{

			// 不能再?广

			return -1;

		}

		for (int v = 0; v < V; ++v)

		{

			h[v] += dist[v];

		}



		// 沿s到t的最短路尽量?广

		int d = f;

		for (int v = t; v != s; v = prevv[v])

		{

			d = min(d, G[prevv[v]][preve[v]].cap);

		}

		f -= d;

		res += d * h[t];

		for (int v = t; v != s; v = prevv[v])

		{

			edge &e = G[prevv[v]][preve[v]];

			e.cap -= d;

			G[v][e.rev].cap += d;

		}

	}

	return res;

}



void clear()

{

	for (int i = 0; i < V; ++i)

	{

		G[i].clear();

	}

}





///////////////////////////SubMain//////////////////////////////////

int main()

{

	scanf("%d%d", &n, &m);

	V = n + 2;

	t = V - 1;

	s = 0;

	int total = 0;

	for (int i = 1; i <= m; i++)

	{

		int x, y, z;

		scanf("%d%d%d", &x, &y, &z);

		x++, y++;

		add_edge(x, y, INF, -z);

		outdegree[x]++, indegree[y]++;

		total += z;

	}



	int max_f = 0;

	for (int i = 1; i <= n; i++)

	{

		if (indegree[i] > outdegree[i])

		{

			add_edge(s, i, indegree[i] - outdegree[i], 0);

			max_f += indegree[i] - outdegree[i];

		}

		else

		{

			add_edge(i, t, outdegree[i] - indegree[i], 0);

		}

	}



	min_cost_flow(1, n, 1);

	add_edge(n, 1, INF, -dist[n]);

	int ans = min_cost_flow(s, t, max_f);

	printf("%d\n", ans - total);

	return 0;

}