#include <fstream>
#include <queue>
#define DIM 80
#define inf 2000000000
using namespace std;
ifstream fin("traseu.in");
ofstream fout("traseu.out");
int n,m,i,mini,nod,a,b,cap,sol,start,fina,pret,j,l;
int c[DIM][DIM], f[DIM][DIM], k[DIM][DIM], z[DIM][DIM],y[DIM];
int d[DIM], t[DIM], h[DIM];
deque<int> co;
vector<int> v[DIM];
 
int bellma()
{
    int nod,vecin;
    for(int i=1;i<=n;i++)
    {
        d[i]=inf;
        h[i]=0;
    }
    d[start]=0;h[start]=1;
    co.clear();co.push_back(start);
    while(!co.empty())
    {
        nod=co.front();
        co.pop_front();
        h[nod]=0;
        for(int i=0;i<v[nod].size();i++)
        {
            vecin=v[nod][i];
            if(c[nod][vecin]>f[nod][vecin]&&d[vecin]>d[nod]+k[nod][vecin])
            {
                d[vecin]=d[nod]+k[nod][vecin];
                t[vecin]=nod;
                if(h[vecin]==0)
                {
                    co.push_back(vecin);
                    h[vecin]=1;
                }
            }
        }
    }
    if(d[fina]==inf)
        return 0;
    else
        return 1;
}
 
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>pret;
        sol+=pret;
        z[a][b]=pret;
        y[a]--;y[b]++;
    }
    for(i=1;i<=n;i++) for(j=1;j<=n;j++)
        if(!z[i][j])
            z[i][j]=10000000;
    for(l=1;l<=n;l++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                 if(i!=j&&j!=l&&l!=i&&z[i][l]!=0&&z[l][j]!=0)
                    z[i][j]=min(z[i][j], z[i][l]+z[l][j]);
            }
    start=1;fina=n+2;
    for(i=1;i<=n;i++)
        if(y[i]!=0)
        {
            if(y[i]>0)
            {
                v[start].push_back(i+1);
                c[start][i+1]=y[i];
            }
            else
            {
                v[i+1].push_back(fina);
                c[i+1][fina]=-y[i];
                v[fina].push_back(i+1);
            }
        }
    for(i=0;i<v[1].size();i++)
        for(j=0;j<v[fina].size();j++)
        {
            v[v[1][i]].push_back(v[fina][j]);
            v[v[fina][j]].push_back(v[1][i]);
            c[v[1][i]][v[fina][j]]=inf;
            k[v[1][i]][v[fina][j]]=z[v[1][i]-1][v[fina][j]-1];
            k[v[fina][j]][v[1][i]]=-z[v[1][i]-1][v[fina][j]-1];
        }
    n+=2;
    while(bellma())
    {
        mini=inf;nod=fina;
        while(t[nod])
        {
            mini=min(mini,c[t[nod]][nod]-f[t[nod]][nod]);
            nod=t[nod];
        }
        nod=fina;
        while(t[nod])
        {
            sol+=mini*k[t[nod]][nod];
            f[t[nod]][nod]+=mini;
            f[nod][t[nod]]-=mini;
            nod=t[nod];
        }
    }
    fout<<sol;
    return 0;
}