#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
#define NM 70
#define INF 0x3f3f3f3f

using namespace std;

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

int Cost[NM][NM], Flux[NM][NM], Cap[NM][NM];
int N, M;
int S, D;
int DI[NM], DO[NM];
int i, j, k;
vector<int> G[NM];
int ANS=0;
int Dist[NM], T[NM];
queue<int> Q;

bool BF ()
{
    int a;
    vector<int>::iterator it;
    memset(Dist, INF, sizeof(Dist));

    Q.push(S);
    Dist[S]=0;

    while (!Q.empty())
    {
        a=Q.front();
        Q.pop();

        for (it=G[a].begin(); it!=G[a].end(); ++it)
            if (Dist[*it]>Dist[a]+Cost[a][*it] && Flux[a][*it]<Cap[a][*it])
            {
                Dist[*it]=Dist[a]+Cost[a][*it];
                T[*it]=a;
                Q.push(*it);
            }
    }

    return Dist[D]<INF;
}

int main ()
{
    f >> N >> M;
    memset(Cost, INF, sizeof(Cost));

    for (i=1; i<=M; i++)
    {
        int a, b, c;
        f >> a >> b >> c;
        DI[b]++; DO[a]++;
        Cost[a][b]=c;
        ANS+=c;
    }

    for (k=1; k<=N; k++)
        for (i=1; i<=N; i++)
            for (j=1; j<=N; j++)
                Cost[i][j]=min(Cost[i][j], Cost[i][k]+Cost[k][j]);

    S=0; D=N+1;
    for (i=1; i<=N; i++)
    {
        if (DI[i]>DO[i])
        {
            G[S].push_back(i);
            G[i].push_back(S);
            Cap[S][i]=DI[i]-DO[i];
            Cost[S][i]=0;
        }
        if (DO[i]>DI[i])
        {
            G[D].push_back(i);
            G[i].push_back(D);
            Cap[i][D]=DO[i]-DI[i];
            Cost[i][D]=0;
        }
    }

    for (i=1; i<=N; i++)
        for (j=1; j<=N; j++)
            if (i!=j && DI[i]>DO[i] && DI[j]<DO[j])
            {
                G[i].push_back(j);
                G[j].push_back(i);
                Cap[i][j]=INF;
                Cost[j][i]=-Cost[i][j];
            }

    while (BF())
    {
        int FMIN=INF;

        for (i=D; i!=S; i=T[i])
            FMIN=min(FMIN, Cap[T[i]][i]-Flux[T[i]][i]);

        for (i=D; i!=S; i=T[i])
        {
            Flux[T[i]][i]+=FMIN;
            Flux[i][T[i]]-=FMIN;
        }

        ANS+=FMIN*Dist[D];
    }

    g << ANS << '\n';

    f.close();
    g.close();

    return 0;
}