#include <bits/stdc++.h>

using namespace std;
ifstream fin("traseu.in");
ofstream fout("traseu.out");
const int nmax = 65;
const int inf = 1000000000;
int N,M,dp[nmax];
int F[nmax][nmax],C[nmax][nmax],Cost[nmax][nmax];
int a[nmax][nmax],st[nmax],dr[nmax],l1,l2;
int in[nmax],out[nmax],S,D,last[nmax];
bool viz[nmax];
long long ans;
queue < int > Q;
vector < int > L[nmax];


inline void Read()
{
   int i,j,k,x,y,z;
   fin >> N >> M;
   for(x = 1; x <= N; x++)
        for(y = 1; y <= N; y++)
            if(x != y) a[x][y] = inf;
   for(i = 1; i <= M; i++)
   {
       fin >> x >> y >> z;
       a[x][y] = min(a[x][y],z);
       out[x]++; in[y]++;
       ans += z;
   }
   for(k = 1; k <= N; k++)
        for(i = 1; i <= N; i++)
            for(j = 1; j <= N; j++)
                a[i][j] = min(a[i][j],a[i][k] + a[k][j]);

}

inline void AddEdge(int x, int y, int capacity, int cost)
{
    L[x].push_back(y); L[y].push_back(x);
    C[x][y] = capacity;
    Cost[x][y] = cost; Cost[y][x] = -cost;
}


inline void BuildG()
{
    int i,j;
    for(i = 1; i <= N; i++)
    {
        if(in[i] > out[i]) st[++l1] = i;
        else if(in[i] < out[i]) dr[++l2] = i;
    }
    S = 0; D = l1 + l2 + 1;
    for(i = 1; i <= l1; i++) AddEdge(S,i,in[st[i]] - out[st[i]],0);
    for(i = 1; i <= l2; i++) AddEdge(l1 + i,D,out[dr[i]] - in[dr[i]],0);
    for(i = 1; i <= l1; i++)
        for(j = 1; j <= l2; j++)
            AddEdge(i,l1 + j,inf,a[st[i]][dr[j]]);
}

inline bool Bellman()
{
    int i,j,nod;
    for(i = 1; i <= D; i++)
    {
        dp[i] = inf;
        viz[i] = false;
    }
    viz[S] = true; dp[S] = 0; Q.push(S);
    while(!Q.empty())
    {
        nod = Q.front(); Q.pop(); viz[nod] = false;
        for(auto it : L[nod])
        {
            if(F[nod][it] < C[nod][it] && dp[it] > dp[nod] + Cost[nod][it])
            {
                dp[it] = dp[nod] + Cost[nod][it];
                last[it] = nod;
                if(viz[it]) continue;
                Q.push(it); viz[it] = true;
            }
        }
    }
    return (dp[D] != inf);
}

inline void Solve()
{
    long long cost = 0;
    int i,x,minflow,ccost;
    while(Bellman())
    {
        minflow = inf;
        ccost = 0;
        for(x = D; x != S; x = last[x])
        {
            minflow = min(minflow,C[last[x]][x] - F[last[x]][x]);
            ccost += Cost[last[x]][x];
        }
        for(x = D; x != S; x = last[x])
        {
            F[last[x]][x] += minflow;
            F[x][last[x]] -= minflow;
        }
        cost += 1LL*dp[D]*minflow;
    }

    fout << ans + cost << "\n";
    fout.close();
}


int main()
{
    Read();
    BuildG();
    Solve();
    return 0;
}