//wish me luck
#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,flow[NMAX][NMAX],dist[NMAX][NMAX],first,last;
int c[NMAX][NMAX],cflow[NMAX][NMAX], father[NMAX], dis[NMAX];
int F[NMAX][NMAX];
bool used[NMAX];
long long ans;
pair <int, int> was[NMAX];
vector <int> v[NMAX], stackf, stackl;
deque <int> q;

long long bellman(){
    int i,node;
    for(i = first ; i <= last ; i++){
        dis[i] = inf;
        father[i] = -1;
        used[i] = 0;
    }
    dis[first] = 0;
    used[first] = 1;
    q.push_back(first);
    while(!q.empty()){
        node = q.front();
        q.pop_front();
        used[node] = 0;

        for(auto it: v[node]){
            if(c[node][it] > F[node][it] && dis[it] > dis[node] + cflow[node][it]){
                dis[it] = dis[node] + cflow[node][it];
                father[it] = node;
                if(!used[it]){
                    used[it] = 1;
                    q.push_back(it);
                }
            }
        }
    }
    if(dis[last] < inf){
        int flow = inf;
        for(i = last ; i != 1 ; i = father[i])
            flow = min(flow, c[father[i]][i] - F[father[i]][i]);
        for(i = last ; i != 1 ; i = father[i]){
            F[father[i]][i] += flow;
            F[i][father[i]] -= flow;
        }
        return flow * dis[last];
    }
    return 0;
}

int main(){
    int i,j,x,y,z,k,node;
    f >> n >> m;
    for(i = 1 ; i <= m ; i++){
        f >> x >> y >> z;
        dist[x][y] = z;
        flow[x][y]++;
        flow[y][x]--;
        was[x].second++;
        was[y].first++;
        ans += z;
    }

    for(k = 1 ; k <= n ; k++)
        for(i = 1 ; i <= n ; i++)
            for(j = 1 ; j <= n ; j++)
                if(dist[i][k] && dist[k][j] && i != j && i != k && j != k && (!dist[i][j] || dist[i][j] > dist[i][k] + dist[k][j]))
                    dist[i][j] = dist[i][k] + dist[k][j];


    first = 0;
    last = n + 1;
    for(i = 1 ; i <= n ; i++){

        if(was[i].first > was[i].second){

            v[first].push_back(i);
            stackf.push_back(i);
            c[first][i] = was[i].first - was[i].second;
            cflow[first][i] = cflow[i][first] = 0;

        }else

            if(was[i].first < was[i].second){

                v[i].push_back(last);
                stackl.push_back(i);
                c[i][last] = was[i].second - was[i].first;
                cflow[i][last] = cflow[last][i] = 0;

            }

    }

    for(int it: stackf)
        for(int its: stackl){

            v[it].push_back(its);
            v[its].push_back(it);
            c[it][its] = inf;
            cflow[it][its] = dist[it][its];
            cflow[its][it] = -dist[it][its];

        }

    int improve = 1;
    while(improve){
        improve = bellman();
        ans += improve;
    }
    g << ans;

    return 0;
}