#include <stdio.h>
#include <vector>
#define nmax 65
#define inf 1000000005
using namespace std;
FILE *f1= fopen("traseu.in", "r");
FILE *f2= fopen("traseu.out", "w");
int n, m, cap[nmax][nmax], cost[nmax][nmax], flux[nmax][nmax], ext[nmax], in[nmax], start, fin, dist[nmax], l[nmax], viz[nmax], prim, ultim, k, coada[100005];
int rez;
vector<int> v[nmax];
void citire()
{
    int i, x, y, c;
    fscanf(f1, "%d%d", &n, &m);
    start=0; fin=n+1;
    for(i=1; i<=m; i++)
    {
        fscanf(f1, "%d%d%d", &x, &y, &c);
        v[x].push_back(y);
        v[y].push_back(x);
        ext[x]++;
        in[y]++;
        cost[x][y]=c;
        cost[y][x]=-c;
        cap[x][y]=inf; ///pe muchie normala poti trimite oricat
        cap[y][x]=0;
        rez+=c;
    }
    for(i=1; i<=n; i++)
    {
        if(in[i]==ext[i]);
        else if(in[i]>ext[i])
        {
            v[start].push_back(i);
            v[i].push_back(start);
            cap[start][i]=in[i]-ext[i];
            cap[i][start]=0;
        }
        else
        {
            v[fin].push_back(i);
            v[i].push_back(fin);
            cap[i][fin]=ext[i]-in[i];
            cap[fin][i]=0;
        }
    }
}
void amelioreaza()
{
    int i, mini=10001;
    for(i=fin; i!=start; i=l[i])
       if(mini> cap[l[i]][i]-flux[l[i]][i])
        mini=cap[l[i]][i]-flux[l[i]][i];
    for(i=fin; i!=start; i=l[i])
    {
        flux[l[i]][i]+=mini;
        flux[i][l[i]]-=mini;
    }
    rez+=dist[fin]*mini;
}
void init()
{
    int i;
    for(i=1; i<=n+1; i++)
    {
        dist[i]=inf;
        l[i]=0;
        viz[i]=0;
    }
    prim=ultim=k=1;
    coada[prim]=start;
    viz[start]=1;
    dist[start]=0;
}
int bellman()
{
    int nod;
    init();
    while(k!=0)
    {
        nod=coada[prim];
        prim++;
        if(prim> 100000) prim=1;
        k--;
        viz[nod]=0;
        for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
            if((!viz[*it])&&(dist[*it]> dist[nod]+ cost[nod][*it])&&(cap[nod][*it]> flux[nod][*it]))
        {
            dist[*it]= dist[nod]+ cost[nod][*it];
            l[*it]=nod;
            if(!viz[*it])
            {
                viz[*it]=1;
                ultim++;
                if(ultim> 100000) ultim=1;
                k++;
                coada[ultim]=*it;
            }
        }
    }
    return (dist[fin]!=inf);
}
void flux_de_ctmin()
{
    while(bellman())
    {
        amelioreaza();
    }
}
int main()
{
    citire();
    flux_de_ctmin();
    fprintf(f2,"%d",  rez);
    return 0;
}