#include <bits/stdc++.h>

using namespace std;

ifstream f("traseu.in");
ofstream g("traseu.out");

const int NMAX = 65;
const int inf = 1e9;
int n,m,mat[NMAX][NMAX],ans;
vector <int> v[NMAX], stacka, stackb;
int in[NMAX], out[NMAX], c[NMAX][NMAX], cost[NMAX][NMAX], last, first;
int father[NMAX], dist[NMAX], used[NMAX], F[NMAX][NMAX];
deque <int> q;

int bellman(){
    int node,i;
    for(i = 0 ; i <= last ; i++){
        father[i] = -1;
        dist[i] = inf;
        used[i] = 0;
    }
    used[0] = 1;
    dist[0] = 0;
    q.push_back(0);
    while(!q.empty()){
        node = q.front();
        q.pop_front();
        used[node] = 0;
        for(auto it: v[node]){
            if(c[node][it] > F[node][it] && dist[it] > dist[node] + cost[node][it]){
                dist[it] = dist[node] + cost[node][it];
                father[it] = node;
                if(!used[it]){
                    q.push_back(it);
                    used[it] = 1;
                }
            }
        }
    }

    if(dist[last] < inf){
        int flow = inf;
        for(i = last ; father[i] != -1 ; i = father[i])
            flow = min(flow, c[father[i]][i] - F[father[i]][i]);
        for(i = last ; father[i] != -1 ; i = father[i]){
            F[father[i]][i] += flow;
            F[i][father[i]] -= flow;
        }
        return flow * dist[last];
    }
    return 0;
}

int main(){
    int i,j,k,x,y,z;
    f >> n >> m;
    for(i = 1 ; i <= n ; i++)
        for(j = 1 ; j <= n ; j++)
            mat[i][j] = inf;

    for(i = 1 ; i <= m ; i++){
        f >> x >> y >> z;
        out[x]++;
        in[y]++;
        mat[x][y] = z;
        ans += z;

    }

    for(k = 1 ; k <= n ; k++)
        for(i = 1 ; i <= n ; i++)
            for(j = 1 ; j <= n ; j++)
                if(mat[i][k] != inf)
                    if(mat[k][j] != inf)
                        if(i != j)
                            if(mat[i][j] > mat[i][k] + mat[k][j])
                                mat[i][j] = mat[i][k] + mat[k][j];

    last = n + 1;
    for(i = 1 ; i <= n ; i++)
        if(in[i] > out[i]){
            v[0].push_back(i);
            c[0][i] = in[i] - out[i];
            cost[0][i] = cost[i][0] = 0;
            stacka.push_back(i);
        }else
            if(in[i] < out[i]){
                v[i].push_back(last);
                c[i][last] = out[i] - in[i];
                cost[last][i] = cost[i][last] = 0;
                stackb.push_back(i);
            }

    for(auto it: stacka)
        for(auto its: stackb){
            v[it].push_back(its);
            v[its].push_back(it);
            c[it][its] = inf;
            cost[it][its] = mat[it][its];
            cost[its][it] = -mat[it][its];
        }

    //now we transmit the maximum flow
    int improve = 1;
    while(improve){
        improve = bellman();
        ans += improve;
    }
    g << ans;

    return 0;
}