#include<bits/stdc++.h>

using namespace std;
ifstream r("traseu.in");
ofstream w("traseu.out");
int n, m, rez, c[63][63], in[36], out[63], f[63][63], parent[63], dist[63];
int bf()
{
    memset(parent, -1, sizeof(parent));
    memset(dist, 0x3f3f3f3f, sizeof(dist));
    dist[0]=0;
    parent[0]=-1;
    int ok=1;
    while(ok==1)
    {
        ok=0;
        for(int i=0; i<=n; i++)
        {
            for(int j=1; j<=n+1; j++)
            {
                if( f[i][j]>0 && dist[j] >(long long)dist[i]+ c[i][j])
                {
                    dist[j]=dist[i] + c[i][j];
                    parent[j]=i;
                    ok=1;
                }
            }
        }
    }
    if( parent[n+1] ==-1){
        return 0;
    }
    return 1;
}
void flux()
{
    int sum=0;
    while(bf())
    {
        int p= n+1, minim=0x3f3f3f3f;
        while(p){
            minim=min(minim, f[parent[p]][p]);
            p=parent[p];
        }
        p=n+1;
        while(p)
        {
            f[parent[p]][p]-=minim;
            f[p][parent[p]]+=minim;
            p=parent[p];
        }
        sum+=dist[n+1]*minim;
    }
    w<<sum+rez;
}
int main ()
{
    memset(c, 0x3f3f3f3f, sizeof(c));
    r>>n>>m;
    for(int i=0;i<m;i++){
        int x, y, co;
        r>>x>>y>>co;
        rez+=co;
        in[y]++;
        out[x]++;
        c[x][y]=co;
        c[y][x]=-co;
        f[x][y]=0x3f3f3f3f;
    }
    for(int i=1;i<=n;i++){
        if(in[i]>out[i]){
            f[0][i]=in[i]-out[i];
            c[0][i]=0;
        }
        if(in[i]<out[i]){
            f[i][n+1]=out[i]-in[i];
            c[i][n+1]=0;
        }
    }
    flux();
	return 0;
}