#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define maxn 65
#define inf 100000000

int n, m, i, j, k, sol, g[maxn];
int c[maxn][maxn], f[maxn][maxn], cost[maxn][maxn], rf[maxn][maxn];
int fol[maxn], t[maxn], dist[maxn];
int q[maxn*maxn*maxn];

int bf()
{
    memset(fol, 0, sizeof(fol));
    for(int i=1; i<=n+1; ++i)
        dist[i]=inf;

    int r=1, nod, fiu, flux=inf;
    q[0]=1;
    q[1]=0;
    fol[0]=1;

    for(int i=1; i<=r; ++i)
    {
        nod=q[i];
        fol[nod]=0;
        for(int j=0; j<=n+1; ++j)
        {
            if(c[nod][j]>f[nod][j] && dist[nod]+cost[nod][j]<dist[j])
            {
                dist[j]=dist[nod]+cost[nod][j];
                t[j]=nod;
                if(fol[j]==0)
                {
                    fol[j]=1;
                    q[++r]=j;
                }
            }
        }
    }

    if(dist[n+1]==inf)
        return 0;

    nod=n+1;
    while(nod)
    {
        flux=min(flux, c[t[nod]][nod]-f[t[nod]][nod]);
        nod=t[nod];
    }

    sol+=flux*dist[n+1];

    nod=n+1;
    while(nod)
    {
        f[t[nod]][nod]+=flux;
        f[nod][t[nod]]-=flux;
        nod=t[nod];
    }

    return 1;
}

int main()
{
    freopen("traseu.in", "r", stdin);
    freopen("traseu.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            rf[i][j]=inf;

    for(int i=1; i<=m; ++i)
    {
        int a, b, cs;
        scanf("%d%d%d", &a, &b, &cs);
        sol+=cs;
        --g[a];
        ++g[b];
        rf[a][b]=min(rf[a][b], cs);
    }

    for(int k=1; k<=n; ++k)
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
                rf[i][j]=min(rf[i][j], rf[i][k]+rf[k][j]);

    for(int i=1; i<=n; ++i)
    {
        if(g[i]>0)
        {
            c[0][i]=g[i];
            for(int j=1; j<=n; ++j)
            {
                if(g[j]>=0)
                    continue;
                c[i][j]=1000000;
                cost[i][j]=rf[i][j];
                cost[j][i]=-rf[i][j];
            }
        }
        if(g[i]<0)
            c[i][n+1]=-g[i];
    }

    while(bf());

    printf("%d\n", sol);

    return 0;
}