#include <bits/stdc++.h>
using namespace std;

class min_cost_flow{
	static const int nmax = 500;
	int cap[nmax][nmax], cost[nmax][nmax];
	vector<vector<vector<int>>> g;
	vector<vector<int>> graph;
	int source, dest;
public:
	min_cost_flow(int s, int d, const vector<vector<vector<int>>>& g):g(g)
	{
		source = s;
		dest = d;
		memset(cap, 0, sizeof(cap));
	}
		
	void build()
	{
		int n = g.size();
		graph.resize(n);
		for(int i = 0;i < n;++i)
		{
			for(size_t j = 0;j < g[i].size();++j)
			{
				int neigh = g[i][j][0];
				graph[i].push_back(neigh);
				graph[neigh].push_back(i);
				cap[i][neigh] = g[i][j][1];
				cost[i][neigh] = g[i][j][2];
				cost[neigh][i] = -g[i][j][2];
			}
		}
	}
	
	bool bellman(int& cost_flow)
	{
		int d[nmax], prev[nmax];
		bool in[nmax];
		const int inf = 1e7;
		
		queue<int> q;
		q.push(source);
		for(int i = 0;i < nmax;++i)
			in[i] = false, d[i] = inf;
		d[source] = 0;
		in[source] = true;
		
		while(!q.empty())
		{
			int nod = q.front();
			q.pop();
			in[nod] = false;
			for(size_t i = 0;i < graph[nod].size();++i)
			{
				int neigh = graph[nod][i];
				if(cap[nod][neigh] > 0 && d[nod] + cost[nod][neigh] < d[neigh])
				{
					d[neigh] = d[nod] + cost[nod][neigh];
					prev[neigh] = nod;
					if(!in[neigh])
					{
						q.push(neigh);
						in[neigh] = true;
					}
				}
			}
		}
		if(d[dest] == inf)
			return false;
		//Get the path back
		int nod = dest, min_cap = inf;
		while(nod != source)
		{
			int pr = prev[nod];
			min_cap = min(min_cap, cap[pr][nod]);
			nod = pr;
		}
		
		nod = dest;
		while(nod != source)
		{
			int pr = prev[nod];
			cap[pr][nod] -= min_cap;
			cap[nod][pr] += min_cap;
			nod = pr;
		}
		cost_flow = min_cap * d[dest];
		return true;
	}
	
	int flow()
	{
		build();
		int cost = 0, ans = 0;
		
		while(bellman(cost))
			ans += cost;
		return ans;
	}
};


int main() {
	freopen("traseu.in", "r", stdin);
	freopen("traseu.out", "w", stdout);
	
	int n, m;
	cin >> n >> m;
	int c[n][n], deg[n], sum = 0;
	const int inf = 1e7;
	
	memset(deg, 0, sizeof(deg));
	for(int i = 0;i < n;++i)
		for(int j = 0;j < n;++j)
			c[i][j] = inf;
	for(int i = 0;i < n;++i)
		c[i][i] = 0;
	
	for(int i = 0;i < m;++i)
	{
		int a, b, cost;
		cin >> a >> b >> cost;
		--a, --b;
		c[a][b] = cost;
		sum += cost;
		++deg[a];
		--deg[b];
	}
	for(int k = 0;k < n;++k)
		for(int i = 0;i < n;++i)
			for(int j = 0;j < n;++j)
				c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
	vector<vector<vector<int>>> g;
	int cnt = 0, mp[n];
	memset(mp, -1, sizeof(mp));
	for(int i = 0;i < n;++i)
		if(deg[i])
			mp[i] = ++cnt;
	cnt += 2;
	g.resize(cnt);
	
	for(int i = 0;i < n;++i)
		if(deg[i] < 0)
		{
			for(int j = 0;j < n;++j)
			{
				if(deg[j] > 0)
					g[mp[i]].push_back({mp[j], inf, c[i][j]});
			}
		}
	for(int i = 0;i < n;++i)
	{
		if(deg[i] < 0)
			g[0].push_back({mp[i], abs(deg[i]), 0});
		else if(deg[i] > 0)
			g[mp[i]].push_back({cnt - 1, deg[i], 0});
	}
	min_cost_flow f(0, cnt - 1, g);
	cout << f.flow() + sum << "\n";
}