#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2100 + 10;
const double EPS = 1e-8;

//max{cx | Ax <= b, x >= 0}
//无解或无&#31351;返回空vector
vector<double> simplex(vector<vector<double> > A, vector<double> b, vector<double> c)
{
	int n = A.size(), m = A[0].size() + 1, r = n, s = m - 1;
	vector<vector<double> > D(n + 2, vector<double>(m + 1, 0));
	vector<int> ix(n + m);
	for (int i = 0; i < n + m; ++ i) ix[i] = i;
	for (int i = 0; i < n; ++ i) {
		for (int j = 0; j < m - 1; ++ j) D[i][j] = -A[i][j];
		D[i][m - 1] = 1;
		D[i][m] = b[i];
		if (D[r][m] > D[i][m]) r = i;
	}
	for (int j = 0; j < m - 1; ++ j) D[n][j] = c[j];
	D[n + 1][m - 1] = -1;
	for (double d; ; ) {
		if (r < n) {
			int t = ix[s]; ix[s] = ix[r + m]; ix[r + m] = t;
			D[r][s] = 1.0 / D[r][s];
			vector<int> speedUp;
			for (int j = 0; j <= m; ++ j) if (j != s) {
				D[r][j] *= -D[r][s];
				if(D[r][j]) {
					speedUp.push_back(j);
				}
			}
			for (int i = 0; i <= n + 1; ++ i) if (i != r) {
				for(int j = 0; j < speedUp.size(); ++ j)
					D[i][speedUp[j]] += D[r][speedUp[j]] * D[i][s];
				D[i][s] *= D[r][s];
			}
		}
		r = -1; s = -1;
		for (int j = 0; j < m; ++ j) if (s < 0 || ix[s] > ix[j]) {
			if (D[n + 1][j] > EPS || (D[n + 1][j] > -EPS && D[n][j] > EPS)) s = j;
		}
		if (s < 0) break;
		for (int i = 0; i < n; ++ i) if (D[i][s] < -EPS) {
			if (r < 0 || (d = D[r][m] / D[r][s] - D[i][m] / D[i][s]) < -EPS || (d < EPS && ix[r + m] > ix[i + m]))
				r = i;
		}
		if (r < 0) return vector<double>(); // 非有界
	}
	if (D[n + 1][m] < -EPS) return vector<double>(); // 无解
	vector<double> x(m - 1);
	for (int i = m; i < n + m; ++ i) if (ix[i] < m - 1) x[ix[i]] = D[i - m][m];
	return x; // &#20540;&#20026;D[n][m]
}

int n, m;
int from[N], to[N], w[N];
int dist[N], deg[N];
vector<pair<int, int> > adj[N];

void bfs()
{
	queue<int> que;
	que.push(0);
	dist[0] = 0;
	for( ; que.size(); ) {
		int u = que.front();
		que.pop();
		for(int e = 0; e < adj[u].size(); ++ e) {
			int v = adj[u][e].first;
			dist[v] = max(dist[v], dist[u] + adj[u][e].second);
			-- deg[v];
			if (deg[v] == 0) {
				que.push(v);
			}
		}
	}
}

void solve()
{
	for(int i = 0; i < n; ++ i) {
		adj[i].clear();
		dist[i] = -1;
		deg[i] = 0;
	}
	for(int i = 0; i < m; ++ i) {
		scanf("%d%d%d", from + i, to + i, w + i);
		adj[from[i]].push_back(make_pair(to[i], w[i]));
		++ deg[to[i]];
	}
	bfs();
	
	int col = n + m;
	int row = 2 * m + n + 2;
	vector<vector<double> > A(row, vector<double>(col));
	vector<double> b(row), c(col);
	for(int i = 0; i < col; ++ i) {
		if (i < n) c[i] = 0;
		else c[i] = 1;
	}
	int cur = 0;
	for(int i = 0; i < m; ++ i) {
		A[cur][i + n] = -1;
		b[cur] = -w[i];
		cur++;
	}
	for(int i = 0; i < n; ++ i) {
		A[cur][i] = -1;
		b[cur] = -dist[i];
		cur++;
	}
	A[cur][0] = 1;
	b[cur++] = 0;
	A[cur][n - 1] = 1;
	b[cur++] = dist[n - 1];
	for(int i = 0; i < m; ++ i) {
		A[cur][from[i]] = 1;
		A[cur][to[i]] = -1;
		A[cur][i + n] = 1;
		b[cur++] = 0;
	}
	vector<double> ret = simplex(A, b, c);
	double answer = 0;
	for(int i = 0; i < m; ++ i) {
		answer += ret[i + n] - w[i];
	}
	printf("%d\n", (int)(answer+1e-2));
}

int main()
{
	for( ; cin >> n >> m; ) {
		solve();
	}
	return 0;
}

Measured memory_bytes: 55652