#include <bits/stdc++.h>
#define maxN 62
#define inf 0x3fffffff
using namespace std;
int n, m, s, d, ans, cost[maxN][maxN], c[maxN][maxN], outd[maxN], ind[maxN];
int D[maxN], prv[maxN], dist[maxN][maxN];
vector < int > V[maxN];
queue < int > q;
bool inq[maxN];
void init()
{
    int i, j;
    for (i = 1; i <= n; ++ i)
        for (j = i + 1; j <= n; ++ j)
            dist[i][j] = dist[j][i] = inf;
}
void read()
{
    int i;
    freopen("traseu.in", "r", stdin);
    scanf("%d %d", &n, &m);
    /// s = 0;
    d = n + 1;
    init();
    for (i = 1; i <= m; ++ i)
    {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        ans += c;
        dist[x][y] = c;
        ++ ind[y];
        ++ outd[x];
    }
}
void RoyFloyd()
{
    int i, j, k;
    for (k = 1; k <= n; ++ k)
        for (i = 1; i <= n; ++ i)
            for (j = 1; j <= n; ++ j)
                if (i != j && i != k && j != k && (dist[i][j] > dist[i][k] + dist[k][j]))
                    dist[i][j] = dist[i][k] + dist[k][j];
}
bool BellmanFord()
{
    int i;
    for (i = 1; i <= n + 1; ++ i)
    {
        D[i] = inf;
        prv[i] = -1;
    }
    memset(inq, 0, sizeof(inq));
    D[s] = 0;
    inq[s] = 1;
    q.push(s);
    while (!q.empty())
    {
        int nod, x = q.front();
        inq[x] = 0;
        q.pop();
        for (i = 0; i < V[x].size(); ++ i)
            if (c[x][nod = V[x][i]] > 0 && D[nod] > D[x] + cost[x][nod])
            {
                D[nod] = D[x] + cost[x][nod];
                prv[nod] = x;
                if (!inq[nod])
                {
                    inq[nod] = 1;
                    q.push(nod);
                }
            }
    }
    if (D[d] != inf)
    {
        int cf = inf;
        for (i = d; i != s; i = prv[i])
            if (c[prv[i]][i] < cf)
                cf = c[prv[i]][i];
        for (i = d; i != s; i = prv[i])
        {
            c[prv[i]][i] -= cf;
            c[i][prv[i]] += cf;
        }
        ans += cf * D[d];
        return 1;
    }
    return 0;
}
void solve()
{
    int i, j;
    RoyFloyd();
    for (i = 1; i <= n; ++ i)
        if (ind[i] > outd[i])
        {
            V[s].push_back(i);
            V[i].push_back(s);
            c[s][i] = ind[i] - outd[i];
            cost[i][s] = cost[i][s] = 0;
            /// cost[s][i] = cost[i][s] = 0;
        }
        else if (ind[i] < outd[i])
        {
            V[d].push_back(i);
            V[i].push_back(d);
            c[i][d] = outd[i] - ind[i];
            cost[i][d] = cost[d][i] = 0;
            /// cost[d][i] = cost[i][d] = 0;
        }
    for (i = 1; i <= n; ++ i)
        if (ind[i] > outd[i])
            for (j = 1; j <= n; ++ j)
                if (ind[j] < outd[j])
                {
                    c[i][j] = inf;
                    V[i].push_back(j);
                    V[j].push_back(i);
                    cost[i][j] = dist[i][j];
                    cost[j][i] = -dist[i][j];
                }
    while (BellmanFord());
}
void write()
{
    freopen("traseu.out", "w", stdout);
    printf("%d\n", ans);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}