// 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;

using T = int;
const T INF = std::numeric_limits<T>::max() / 4;

struct MFMC {
  struct Edge { int to, rev; T cap, cost, flow; };

  int n;
  std::vector<std::vector<Edge> > graph;
  std::vector<int> par;
  std::vector<T> dist, pi;
  std::vector<Edge> es;
  std::priority_queue<std::pair<T, int> > pq;

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

  void AddEdge(int a, int b, T cap, T cost, T flow = 0) {
    graph[a].push_back({b, (int)graph[b].size(), cap, cost, flow});
    graph[b].push_back({a, (int)graph[a].size() - 1, 0, -cost, -flow});
  }
  bool relax(int from, const Edge& e) {
    if (dist[from] == INF) return false;
    T 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) {
    dist.assign(n, INF); 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);
    return par[t] != -1;
  }
  std::pair<T, T> Compute(int s, int t) {
    T flow = 0, cost = 0;
    while (dijkstra(s, t)) {
      T now = INF;
      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); 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;
			G[i][j]=INF;
		}
	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 F(N*2+2);
	for(i=0;i<N;++i)
	{
		in=out=0;
		for(j=0;j<N;++j)
		{
			in+=(G[j][i]<INF);
			out+=(G[i][j]<INF);
		}

		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)
				F.AddEdge(i, N+j, NMAX, H[i][j]);

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

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

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