#include <bits/stdc++.h>
using namespace std;

int n, m;
int d[65], old[65], reald[65], TT[65];
int cost[65][65], C[65][65];
bool inq[65];
int Fc, gr[65];
vector <int> v[65];
queue <int> q;
priority_queue <pair <int, int> > pq;

inline bool dijkstra(){
    memset(d, 0x3f, sizeof(d));
    d[0] = 0; reald[0] = 0;
    pq.push({0, 0});

    while(!pq.empty()){
        int nod = pq.top().second;
        pq.pop();
        for(auto it : v[nod]){
            if(!C[nod][it]) continue ;
            if(d[it] > d[nod] + cost[nod][it] + old[nod] - old[it]){
                d[it] = d[nod] + cost[nod][it] + old[nod] - old[it];
                reald[it] = reald[nod] + cost[nod][it];
                pq.push({-d[it], it});
                TT[it] = nod;
            }
        }
    }

    memcpy(old, reald, sizeof(old));
    if(d[n + 1] == 0x3f3f3f3f) return false;

    int Minf = 2000000000, cst = 0;
    for(int w = n + 1; w != 0 ; w = TT[w]){
        Minf = min(Minf, C[TT[w]][w]);
        cst += cost[TT[w]][w];
    }

    Fc += Minf * reald[n + 1];

    for(int w = n + 1; w != 0 ; w = TT[w]){
        C[TT[w]][w] -= Minf;
        C[w][TT[w]] += Minf;
    }
    return true;
}
int main()
{
    freopen("traseu.in", "r", stdin);
    freopen("traseu.out", "w", stdout);

    scanf("%d%d", &n, &m);
    int x, y, z;
    for(int i = 1; i <= n ; ++i) for(int j = 1; j <= n ; ++j) if(i != j)cost[i][j] = 1000000000;
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d%d", &x, &y, &z);
        cost[x][y] = z;
        --gr[x]; ++gr[y];
        Fc += z;
    }

    for(int k = 1; k <= n ; ++k){
        for(int i = 1; i <= n ; ++i){
            for(int j = 1; j <= n ; ++j){
                if(cost[i][k] && cost[k][j]){
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
                }
            }
        }
    }

    for(int i = 1; i <= n ; ++i)
        if(gr[i] > 0) v[0].push_back(i), C[0][i] = gr[i];
        else v[i].push_back(n + 1), C[i][n + 1] = -gr[i];

    for(int i = 1; i <= n ; ++i){
        if(gr[i] > 0)
        for(int j = 1; j <= n ; ++j){
            if(gr[j] < 0){
                v[i].push_back(j);
                C[i][j] = 2000000000;
                cost[j][i] = -cost[i][j];
            }
        }
    }


    while(dijkstra()) ;

    printf("%d", Fc);
    return 0;
}