#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#include <functional>
#include <iterator>
#include <locale>
#include <memory>
#include <stdexcept>
#include <utility>
#include <string>
#include <fstream>
#include <ios>
#include <iostream>
#include <iosfwd>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <streambuf>
#include <complex>
#include <numeric>
#include <valarray>
#include <exception>
#include <limits>
#include <new>
#include <typeinfo>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <climits>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdlib>
#include <cstddef>
#include <cstdarg>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <cwchar>
#include <cwctype>
using namespace std;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);
typedef long long ll;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define ALL(c) (c).begin(), (c).end()

// 最小費用流
// 負閉路にも対応している

// Spaghetti Source - グラフの基本要素
// http://www.prefield.com/algorithm/graph/graph.html
struct Edge {
	int src;
	int dst;
	int weight;
	int flow;
	Edge(int s, int d, int w, int f) : src(s), dst(d), weight(w), flow(f) {}
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
		e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef list<Edge> Edges;
typedef vector<Edges> Graph;

// Spaghetti Source - 単一始点最短路 (Bellman Ford)
// http://www.prefield.com/algorithm/graph/bellman_ford.html
static const int INF = INT_MAX / 2;
static const int NEGATIVE_CYCLE = INT_MIN / 2;
bool bellmanFord(const Graph& g, int s, vector<int>& dist, vector<int>& prev) {
	const int n = g.size();
	dist.assign(n, INF);
	dist[s] = 0;
	prev.assign(n, -2);
	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i) {
			for (list<Edge>::const_iterator e = g[i].begin(); e != g[i].end(); ++e) {
				if (dist[e->dst] > dist[e->src] + e->weight) {
					dist[e->dst] = dist[e->src] + e->weight;
					prev[e->dst] = e->src;
					if (k == n - 1) {
						dist[e->dst] = NEGATIVE_CYCLE;
						return false;
					}
				}
			}
		}
	}
	return true;
}
vector<int> buildPath(const vector<int> &prev, int t) {
	vector<bool> memo(prev.size(), false);
	vector<int> path;
	for (int u = t; u >= 0 ; u = prev[u]) {
		if (memo[u]) {
			path.erase(path.begin(), find(path.begin(), path.end(), u));
			path.push_back(u);
			break;
		}

		memo[u] = true;
		path.push_back(u);
	}
	reverse(path.begin(), path.end());
	return path;
}

void updatePath(Graph& g, const vector<int>& path, int& restFlow, int& totalWeight, int& totalFlow)
{
	int bestFlow = restFlow;
	for (int i = 0; i < path.size() - 1; ++i) {
		// 一番コストの低い枝で更新する
		const int from = path[i];
		const int to = path[i + 1];
		int bestWeight = INT_MAX;
		int localBestFlow = 0;
		for (Edges::iterator it = g[from].begin(); it != g[from].end(); ++it) {
			if (it->src == from && it->dst == to && bestWeight > it->weight) {
				bestWeight = it->weight;
				localBestFlow = it->flow;
			}
		}

		if (bestFlow > localBestFlow) {
			bestFlow = localBestFlow;
		}
	}

	restFlow -= bestFlow;

	////Debug
	//printf("bestFlow:%d\n", bestFlow);

	for (int i = 0; i < path.size() - 1; ++i) {
		const int from = path[i];
		const int to = path[i + 1];

		int bestWeight = INT_MAX;
		list<Edge>::iterator edge = g[from].end();
		for (list<Edge>::iterator it = g[from].begin(); it != g[from].end(); ++it) {
			if (it->src == from && it->dst == to && bestWeight > it->weight) {
				bestWeight = it->weight;
				edge = it;
			}
		}

		assert(edge != g[from].end());

		edge->flow -= bestFlow;

		if (edge->flow == 0) {
			g[from].erase(edge);
		}

		edge = g[to].end();
		for (list<Edge>::iterator it = g[to].begin(); it != g[to].end(); ++it) {
			if (it->src == to && it->dst == from && it->weight == -bestWeight) {
				edge = it;
				break;
			}
		}

		if (edge == g[to].end()) {
			g[to].push_back(Edge(to, from, -bestWeight, bestFlow));
		} else {
			edge->flow += bestFlow;
		}

		totalWeight += bestFlow * bestWeight;

		////Debug
		//printf("%d -> %d (%d)\n", from, to, bestWeight);
	}

	if (path.front() != path.back()) {
		totalFlow += bestFlow;
	}
}

// <費用, フロー>
pair<int, int> minimumCostFlow(Graph &g, int s, int t, int restFlow) {
	int totalWeight = 0;
	int totalFlow = 0;
	const int n = g.size();
	for (;;) {
		//ステップ０：人工問題を解いて、需要供給量を満たすフローを求める
		//ステップ１：現在のフローに関する残余ネットワークを作る
		vector<int> label(n, -2);
		label[s] = -1;
		bool updated = true;
		while (updated) {
			updated = false;
			for (Graph::iterator it = g.begin(); it != g.end(); ++it) {
				for (Edges::iterator jt = it->begin(); jt != it->end(); ++jt) {
					if (label[jt->src] != -2 && label[jt->dst] == -2) {
						label[jt->dst] = jt->src;
						updated = true;
					}
				}
			}
		}

		if (label[t] == -2 || restFlow == 0) {
			//ステップ２：残余ネットワークに費用が負の閉路が存在しない⇒ 現在のフローは費用最小（終了）
			vector<int> dist;
			vector<int> prev;
			bellmanFord(g, s, dist, prev);
			if (find(dist.begin(), dist.end(), NEGATIVE_CYCLE) == dist.end()) {
				break;
			}

			//ステップ３：残余ネットワークの費用が負の閉路を求め、それを用いて現在のフローを更新する
			int cycleStart = (int)distance(dist.begin(), find(dist.begin(), dist.end(), NEGATIVE_CYCLE));
			vector<int> path = buildPath(prev, cycleStart);
			int tempRestFlow = INT_MAX;
			updatePath(g, path, tempRestFlow, totalWeight, totalFlow);

			//ステップ４：ステップ１へ戻る

		} else {
			vector<int> path;
			int current = t;
			while (current != -1) {
				path.push_back(current);
				current = label[current];
			}

			reverse(path.begin(), path.end());

			updatePath(g, path, restFlow, totalWeight, totalFlow);
		}
	}

	return make_pair(totalWeight, totalFlow);
}

int dfs(const Graph& dag, int current, vector<int>& dp) {
	int& cost = dp[current];
	if (cost == 0) {
		for (Edges::const_iterator it = dag[current].begin(), itEnd = dag[current].end(); it != itEnd; ++it) {
			cost = max(cost, it->weight + dfs(dag, it->dst, dp));
		}
	}
	return cost;
}

static const int kInf = INT_MAX / 10000;
static const int kMin = INT_MIN / 10000;

int main() {
	for (int N, M; cin >> N >> M && (N || M); ) {
		Graph dag(N);
		REP(m, M) {
			int src, dst, cost;
			cin >> src >> dst >> cost;
			dag[src].push_back(Edge(src, dst, cost, 0));
		}

		vector<int> dp(N);
		dfs(dag, 0, dp);
		const int D = dp[0];

		//Graph g(N * 2 + 1);
		//REP(n, N) {
		//	g[n + N].push_back(Edge(n + N, n, 0, 1));
		//}

		//REP(n, N) {
		//	for (Edges::const_iterator it = dag[n].begin(), itEnd = dag[n].end(); it != itEnd; ++it) {
		//		g[it->src].push_back(Edge(it->src, it->dst, -it->weight, kInf));
		//		g[it->src].push_back(Edge(it->src, it->dst + N, -it->weight + kMin, 1));
		//	}
		//}
		//g[(N - 1) * 2].push_back(Edge(N - 1, N * 2, D, kInf));

		//const int w = minimumCostFlow(g, 0, N - 1, kInf).first;
		//cout << -(w - kMin * N) << endl;

		Graph g(N + 1);
		REP(n, N) {
			for (Edges::const_iterator it = dag[n].begin(), itEnd = dag[n].end(); it != itEnd; ++it) {
				g[it->src].push_back(Edge(it->src, it->dst, -it->weight, kInf));
				g[it->src].push_back(Edge(it->src, it->dst, -it->weight + kMin, 1));
			}
		}
		g[N - 1].push_back(Edge(N - 1, N, D, kInf));

		const int w = minimumCostFlow(g, 0, N, kInf).first;
		cout << w - kMin * M << endl;
	}
}