#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("traseu.in");
ofstream fout("traseu.out");
#define INF (1<<29)
#define MAX 63
#define mp make_pair
#define pb push_back

typedef vector <int> :: iterator ite;
typedef vector < pair<int, int> > :: iterator iter;
vector <pair <int, int> > G[MAX];
vector <int> D[MAX];
priority_queue <pair <int , int> > Q;
queue <int> Qu;
int n;
int dist[MAX], in[MAX], out[MAX], C[MAX][MAX], F[MAX][MAX], Ca[MAX][MAX], dad[MAX];
int flow;

void dis(int nod)
{
    int i;
    for(i=1;i<=n;i++)
    {
        dist[i]=INF;
    }
    dist[nod]=0;
    Q.push(mp(0, nod));
    while(Q.size())
    {
        nod=Q.top().second;
        Q.pop();
        for(iter it=G[nod].begin();it!=G[nod].end();it++)
        {
            if(dist[it->first]>dist[nod]+it->second)
            {
                dist[it->first]=dist[nod]+it->second;
                Q.push(mp(-dist[it->first], it->first));
            }
        }
    }
}

int bellford()
{
    int minim, i, nod;
    for(i=0;i<=n+1;i++)
        dist[i]=INF;
    dist[0]=0;
    Qu.push(0);
    while(Qu.size())
    {
        nod=Qu.front();
        Qu.pop();
        for(ite it=D[nod].begin();it!=D[nod].end();it++)
        {
            if(dist[*it]>dist[nod]+C[nod][*it] && F[nod][*it]<Ca[nod][*it])
            {
                dist[*it]=dist[nod]+C[nod][*it];
                Qu.push(*it);
                dad[*it]=nod;
            }
        }
    }

    if(dist[n+1]==INF)
        return 0;
    minim=INF;
    for(i=n+1;i;i=dad[i])
    {
        minim=min(minim, Ca[dad[i]][i]-F[dad[i]][i]);
    }
    for(i=n+1;i;i=dad[i])
    {
        flow+=minim*C[dad[i]][i];
        F[dad[i]][i]+=minim;
        F[i][dad[i]]-=minim;
    }
    return 1;
}

int main()
{
    int m, l, x, y, c, i;
    fin>>n;
    fin>>m;
    l=0;
    while(m--)
    {
        fin>>x>>y>>c;
        l+=c;
        G[x].pb(mp(y, c));
        in[y]++;
        out[x]++;
    }
    for(i=1;i<=n;i++)
    {
        if(in[i]>out[i])
        {
            D[0].pb(i);
            D[i].pb(0);
            Ca[0][i]=in[i]-out[i];
        }
        if(out[i]>in[i])
        {
            D[n+1].pb(i);
            D[i].pb(n+1);
            Ca[i][n+1]=out[i]-in[i];
        }
    }
    for(ite it=D[0].begin();it!=D[0].end();it++)
    {
        dis(*it);
        for(ite iti=D[n+1].begin();iti!=D[n+1].end();iti++)
        {
            D[*it].pb(*iti);
            D[*iti].pb(*it);
            Ca[*it][*iti]=INF;
            C[*it][*iti]=dist[*iti];
            C[*iti][*it]=-dist[*iti];
        }
    }
    while(bellford());
    fout << l + flow;
}