#include <fstream>
#include <queue>
#define N 200
#define oo 0x3f3f3f3f
using namespace std;

int flow, sol, n, m, i, j, k, x, y, z, S, D;
int prev[N], Drum[N][N], Dist[N], C[N][N], Cost[N][N], in[N], out[N];
bool inq[N];
queue <int> Q;

bool Bellman()
{
    for(i = 0; i <= D; i++) Dist[i] = oo;
    Dist[S] = 0;
    Q.push(S);
    while(!Q.empty())
    {
        x = Q.front();
        inq[x] = 0;
        Q.pop();
        for(i = 0; i <= D; i++)
            if(C[x][i] and Dist[i] > Dist[x] + Cost[x][i])
            {
                Dist[i] = Dist[x] + Cost[x][i];
                prev[i] = x;
                if(!inq[i])
                {
                    inq[i] = 1;
                    Q.push(i);
                }
            }
    }
    return Dist[D] != oo;
}

int main()
{
    ifstream fi("traseu.in");
    ofstream fo("traseu.out");
    fi >> n >> m;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            Drum[i][j] = oo;

    for(i = 1; i <= m; i++)
    {
        fi >> x >> y >> z;
        sol += z;
        in[y]++; out[x]++;
        Drum[x][y] = z;
    }
    for(k = 1; k <= n; k++)
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                    if(i != k and j !=k and Drum[i][k] + Drum[k][j] < Drum[i][j])
                        Drum[i][j] = Drum[i][k] + Drum[k][j];
    S = 0; D = 2*n+1;
    for(i = 1; i <= n; i++)
    {
        if(out[i] < in[i]) C[S][i] = in[i] - out[i];
        if(in[i] < out[i]) C[n+i][D] = out[i] - in[i];
    }
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            if(out[i] < in[i] and out[j] > in[j] and Drum[i][j] != oo)
            {
                C[i][n+j] = oo;
                Cost[i][n+j] = Drum[i][j];
                Cost[n+j][i] = -Drum[i][j];
            }
    while(Bellman())
    {
        flow = oo;
        for(i = D; i != S; i = prev[i])
            flow = min(flow, C[prev[i]][i]);
        for(i = D; i != S; i = prev[i])
            C[prev[i]][i] -= flow, C[i][prev[i]] += flow;
        sol += flow*Dist[D];
    }
    fo << sol << "\n";
    return 0;
}