#include<cstdio>
#include<queue>
#include<vector>

using namespace std;

int n, X, Y, m, N, S, D, t[65], ap[65], cod[65], in_deg[65], out_deg[65];
long long INF, answer, bell[65], bani[65][65], roy[65][65], f[65][65], c[65][75];
vector < int > v[65];

bool bellman()
{
    for (int i=1; i<=N; i++)
    {
        bell[i] = INF;
        ap[i] = 0;
        t[i] = -1;
    }
    queue < int > q;
    q.push(S);
    t[S] = 0;
    bell[S] = 0;
    ap[S] = 1;
    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        ap[nod] = 0;
        for (vector < int > :: iterator it = v[nod].begin(); it != v[nod].end(); it++)
            if (f[nod][*it] < c[nod][*it] && bell[nod] + bani[nod][*it] < bell[*it])
            {
                bell[*it] = bell[nod] + bani[nod][*it];
                t[*it] = nod;
                if (ap[*it] == 0)
                {
                    q.push(*it);
                    ap[*it] = 1;
                }
            }
    }
    return (t[D] != -1);
}

long long calc_flux()
{
    long long cost = 0;
    while (bellman())
    {
        long long fmin = INF;
        for (int i=D; i!=S; i=t[i])
            if (c[t[i]][i] - f[t[i]][i] < fmin)
                fmin = c[t[i]][i] - f[t[i]][i];
        cost += 1LL * fmin * bell[D];
        for (int i=D; i!=S; i=t[i])
        {
            f[t[i]][i] += fmin;
            f[i][t[i]] -= fmin;
        }
    }
    return cost;
}

void Add_Edge (int x, int y, long long cap, long long ban)
{
    if (x==y) return ;
    v[x].push_back(y);
    v[y].push_back(x);
    c[x][y] = cap;
    bani[x][y] = ban;
    bani[y][x] = -ban;
}

void Build_Graph()
{
    N = S = 1;
    for (int i=1; i<=n; i++)
        if (in_deg[i] > out_deg[i])
        {
            N ++;
            Add_Edge(S, N, in_deg[i] - out_deg[i], 0);
            cod[i] = N;
        }

    for (int i=1; i<=n; i++)
        if (in_deg[i] < out_deg[i])
            cod[i] = ++N;

    D = ++N;
    for (int i=1; i<=n; i++)
        if (in_deg[i] < out_deg[i])
            Add_Edge (cod[i], D, out_deg[i] - in_deg[i], 0);

    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            if (in_deg[i] > out_deg[i] && in_deg[j] < out_deg[j] && roy[i][j] < INF)
                Add_Edge (cod[i], cod[j], 10000, roy[i][j]);
}

int main()
{
freopen ("traseu.in", "r", stdin);
freopen ("traseu.out", "w", stdout);
INF = (1LL<<52);
scanf ("%d", &n);
scanf ("%d", &m);
for (int i=1; i<=n; i++)
    for (int j=1; j<=n; j++)
        if (i!=j) roy[i][j] = INF;
for (int i=1; i<=m; i++)
{
    scanf ("%d %d", &X, &Y);
    scanf ("%lld", &roy[X][Y]);
    out_deg[X] ++;
    in_deg[Y] ++;
    answer += roy[X][Y];
}
for (int k=1; k<=n; k++)
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            if (roy[i][k] + roy[k][j] < roy[i][j])
                roy[i][j] = roy[i][k] + roy[k][j];
Build_Graph ();
printf ("%lld\n", answer + calc_flux());
return 0;
}