#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DIM 65

using namespace std;

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

int n, m, ans, dist[DIM], in[DIM], out[DIM], d[DIM][DIM], t[DIM], C[DIM][DIM], F[DIM][DIM], cost[DIM][DIM], sursa, dest;
queue <int> q;
bitset <DIM> iq;
vector <int> edges[DIM];

bool bf()
{
    int ok = 0;
    for(int i = sursa; i <= dest; i++)
        dist[i] = INF;
    iq.reset();
    q.push(sursa);
    dist[sursa] = 0;
    iq[sursa] = 1;
    while(!q.empty())
    {
        int nod = q.front();
        iq[nod] = 0;
        q.pop();
        for(auto child : edges[nod])
            if(dist[child] > dist[nod] + cost[nod][child] && C[nod][child] > F[nod][child])
            {
                dist[child] = dist[nod] + cost[nod][child];
                if(!iq[child])
                {
                    iq[child] = 1;
                    q.push(child);
                }
                if(child == dest)
                    ok = 1;
                t[child] = nod;
            }
    }
    return ok;
}

int main()
{
    f >> n >> m;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cost[i][j] = d[i][j] = INF;

    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        f >> x >> y >> c;
        d[x][y] = c;
        out[x]++;
        in[y]++;
        ans += c;
    }

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(i != j && j != k && i != k && d[i][k] != INF && d[k][j] != INF)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    sursa = 0, dest = n + 1;
    for(int i = 1; i <= n; i++)
        if(out[i] < in[i])
        {
            edges[i].push_back(sursa);
            edges[sursa].push_back(i);
            C[sursa][i] = in[i] - out[i];
        }
        else if(in[i] < out[i])
        {
            edges[i].push_back(dest);
            edges[dest].push_back(i);
            C[i][dest] = out[i] - in[i];
        }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(out[i] < in[i] && out[j] > in[j])
            {
                edges[i].push_back(j);
                edges[j].push_back(i);
                cost[i][j] = d[i][j];
                cost[j][i] = -d[i][j];
                C[i][j] = INF;
            }

    while(bf())
    {
        int k = dest, mini = INF;
        while(k)
        {
            mini = min(mini, C[t[k]][k] - F[t[k]][k]);
            k = t[k];
        }

        k = dest;
        while(k)
        {
            F[t[k]][k] += mini;
            F[k][t[k]] -= mini;
            k = t[k];
        }
        ans += dist[dest] * mini;
    }

    g << ans;
    return 0;
}