#include <cstdio>
#include <vector>

using namespace std;

#define Nmax 64
#define INF 0x3f3f3f3f
#define pb push_back
#define sz size()

int n, m, s, d, best;
int cost[Nmax][Nmax], gri[Nmax], gro[Nmax], v[Nmax], dist[Nmax], c[Nmax][Nmax], cd[Nmax * Nmax], t[Nmax];
vector<int> lv[Nmax];


void citire()
{
    int i, a, b, c;
    scanf("%d %d\n", &n, &m);
    
    memset(cost, 0x3f, sizeof(cost));
    for (i = 1; i <= n; ++i)
        cost[i][i] = 0;
    
    for (i = 1; i <= m; ++i)
    {
        scanf("%d %d %d\n", &a, &b, &c);
        cost[a][b] = c;
        ++gro[a]; ++gri[b];
        best += c;
    }
}

int bellman_ford()
{
    int st, dr, i, lim, nod;
    
    memset(v, 0, sizeof(v));
    memset(dist, 0x3f, sizeof(dist));
    
    cd[dr = 1] = s;
    st = 0;
    dist[s] = 0;
    v[s] = 1;
    
    while (st < dr)
    {
        nod = cd[++st];
        lim = lv[nod].sz;
        v[nod] = 0;
        
        for (i = 0; i < lim; ++i)
        if (c[nod][lv[nod][i]] > 0 && dist[nod] + cost[nod][lv[nod][i]] < dist[lv[nod][i]])
            {
                dist[lv[nod][i]] = dist[nod] + cost[nod][lv[nod][i]];
                t[lv[nod][i]] = nod;
                if (!v[lv[nod][i]])
                {
                    v[lv[nod][i]] = 1;
                    cd[++dr] = lv[nod][i];
                }
            }
    }
    
    if (dist[d] < INF / 2)
        return 1;
    else
        return 0;
}

void flux()
{
    int nod, val;
    
    while (bellman_ford())
    {
        val = INF;
        for (nod = d; nod != s; nod = t[nod])
            val = min(val, c[t[nod]][nod]);
        
        best += dist[d] * val;
        
        for (nod = d; nod != s; nod = t[nod])
        {
            c[t[nod]][nod] -= val;
            c[nod][t[nod]] += val;
        }
    }
}

void solve()
{
    int i, j, k;
    for (k = 1; k <= n; ++k)
        for (i = 1; i <= n; ++i)
            for (j = 1; j <= n; ++j)
                if (cost[i][k] + cost[k][j] < cost[i][j])
                    cost[i][j] = cost[i][k] + cost[k][j];
    
    s = 0;
    d = n + 1;
    
    for (i = 1; i <= n; ++i)
        if (gri[i] > gro[i])
        {
            lv[s].pb(i);
            lv[i].pb(s);
            c[s][i] = gri[i] - gro[i];
        }
        else if (gri[i] < gro[i])
        {
            lv[i].pb(d);
            lv[d].pb(i);
            c[i][d] = gro[i] - gri[i];
        }
    
    for (i = 1; i <= n; ++i)
    if (gri[i] > gro[i])
        for (j = 1; j <= n; ++j)
        if (gri[j] < gro[j])
        {
            lv[i].pb(j);
            lv[j].pb(i);
            c[i][j] = INF;
            cost[j][i] = - cost[i][j];
        }
    
    for (i = 0; i <= d; ++i)
    {
        cost[s][i] = cost[i][s] = 0;
        cost[i][d] = cost[d][i] = 0;
    }
    
    flux();
    
    printf("%d\n", best);
}

int main()
{
    freopen("traseu.in", "r", stdin);
    freopen("traseu.out", "w", stdout);
    citire();
    solve();
    return 0;
}