// Ilie "The-Winner" Dumitru
// Dumnezeu sa o ierte
#include<bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using ll=long long;
constexpr int NMAX=64;
constexpr ll MOD=1000000009;

template<class T> constexpr T INF() {return std::numeric_limits<T>::max()/4;};
template<class F, class C>
struct MFMC {
	struct Edge { int to, rev; F cap, flow; C cost; };

	int n;
	std::vector<std::vector<Edge> > graph;
	std::vector<int> par;
	std::vector<C> dist;
	std::vector<C> pi;
	std::vector<Edge> es;

	MFMC(int n) : n(n), graph(n), par(n), dist(n), pi(n) {}

	void AddEdge(int a, int b, F cap, C cost, F flow = 0) {
		graph[a].push_back({b, sz(graph[b]), cap, flow, cost});
		graph[b].push_back({a, sz(graph[a])-1, 0, -flow, -cost});
	}
	bool relax(int from, const Edge& e) {
		if (dist[from] == INF<C>()) return false;
		auto now = dist[from] + pi[from] - pi[e.to] + e.cost;
		if (e.flow < e.cap && now < dist[e.to])
			return dist[e.to] = now, par[e.to] = e.rev, true;
		return false;
	}
	bool dijkstra(int s, int t) {
		std::priority_queue<std::pair<C, int> > pq;

		dist.assign(n, INF<C>()); par.assign(n, -1);
		dist[s] = 0; pq.emplace(0, s);
		while (!pq.empty()) {
			auto [d, node] = pq.top(); pq.pop();
			if (dist[node] != -d) continue;
			for (auto& e : graph[node])
				if (relax(node, e))
					pq.emplace(-dist[e.to], e.to);
		}
		for (int i = 0; i < n; ++i)
			pi[i] = std::min(pi[i] + dist[i], INF<C>());
		return par[t] != -1;
	}
	std::pair<F, C> Compute(int s, int t) {
		F flow = 0; C cost = 0;
		while (dijkstra(s, t)) {
			F now = INF<F>();
			for (int phase : {0, 1}) {
				for (int node = t; node != s; ) {
					auto& e1 = graph[node][par[node]];
					auto& e2 = graph[e1.to][e1.rev];
					if (!phase) now = std::min(now, e2.cap - e2.flow);
					else e2.flow += now, e1.flow -= now;
					node = e1.to;
				}
			}
			flow += now;
			cost += pi[t]*now;
		}
		return {flow, cost};
	}
	// If some costs can be negative, call this before maxflow:
	void SetPi(int s) { // (otherwise, leave this out)
		dist.assign(n, INF<C>()); dist[s] = 0;
		int it = n, ch = 1;
		while (ch-- && it--)
			for (int i = 0; i < n; ++i)
				for (auto& e : graph[i])
					ch |= relax(i, e);
		assert(it >= 0); // negative cost cycle
		pi = dist;
	}
};

int N, M;
int G[NMAX][NMAX];
int H[NMAX][NMAX];

int main()
{
	FILE* f=fopen("traseu.in", "r"), *g=fopen("traseu.out", "w");
	int i, j, k, a, b, c, tot=0, in, out;

	fscanf(f, "%d%d", &N, &M);
	for(i=0;i<N;++i)
		for(j=0;j<N;++j)
		{
			H[i][j]=(i!=j)*INF<int>();
			G[i][j]=INF<int>();
		}
	for(i=0;i<M;++i)
	{
		fscanf(f, "%d%d%d", &a, &b, &c);
		--a;
		--b;
		G[a][b]=H[a][b]=c;
		tot+=c;
	}

	for(k=0;k<N;++k)
		for(i=0;i<N;++i)
			for(j=0;j<N;++j)
				H[i][j]=std::min(H[i][j], H[i][k]+H[k][j]);

	MFMC<int, int> F(N*2+2);
	for(i=0;i<N;++i)
	{
		in=out=0;
		for(j=0;j<N;++j)
		{
			in+=(G[j][i]<INF<int>());
			out+=(G[i][j]<INF<int>());
		}

		if(in>out)
			F.AddEdge(N*2, i, in-out, 0);
		else if(in<out)
			F.AddEdge(i+N, N*2+1, out-in, 0);
	}

	for(i=0;i<N;++i)
		for(j=0;j<N;++j)
			if(H[i][j]>0 && H[i][j]<INF<int>())
				F.AddEdge(i, N+j, NMAX, H[i][j]);

	auto p=F.Compute(N*2, N*2+1);
	tot+=p.second;

	fprintf(g, "%d\n", tot);

	fclose(f);
	fclose(g);
	return 0;
}