#include <fstream>
#include <queue>
#include <vector>

using namespace std;
ifstream f("traseu.in");
ofstream g("traseu.out");
int n,m;
const int N=63;
int st,dr,X,Y,Z;
int intrare[N],iesire[N];
vector<int>a[N];
int d[N][N],dist[N];
bool viz[N];
int dad[N],flx[N][N];
int blm(int st,int dr)
{
    for(int i=0;i<=n+2;i++)
    {
        dad[i]=0;
        viz[i]=false;
        dist[i]=1e9;
    }
    queue<int>q;
    q.push(st);
    viz[st]=true;
    dist[st]=0;
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
        viz[nod]=false;
        for(auto x: a[nod])
        {
            if(dist[x]>dist[nod]+d[nod][x]&&flx[nod][x]>0)
            {
                dist[x]=dist[nod]+d[nod][x];
                dad[x]=nod;
                if(viz[x]==false)
                {
                    viz[x]=true;
                    q.push(x);
                }
            }
        }
    }
    return dist[dr];
}
int main()
{
    f>>n>>m;
    st=0;dr=n+1;
    int val=0;
    for(int i=1;i<=m;i++)
    {
        f>>X>>Y>>Z;
        val+=Z;
        a[X].push_back(Y);
        a[Y].push_back(X);
        d[X][Y]=Z;
        d[Y][X]=-Z;
        flx[X][Y]=1e3;
        intrare[Y]++;
        iesire[X]++;
    }
    for(int i=1;i<=n;i++)
        if(intrare[i]>iesire[i])
        {
            a[st].push_back(i);
            a[i].push_back(st);
            flx[st][i]=intrare[i]-iesire[i];
        }
    for(int i=1;i<=n;i++)
        if(intrare[i]<iesire[i])
        {
            a[dr].push_back(i);
            a[i].push_back(dr);
            flx[i][dr]=iesire[i]-intrare[i];
        }
    while(true)
    {
        int sum=blm(st,dr);
        if(sum==1e9)
            break;
        int mn=1e9;
        for(int i=dr;i!=st;i=dad[i])
        {
            mn=min(mn,flx[dad[i]][i]);
        }
        for(int i=dr;i!=st;i=dad[i])
        {
            flx[dad[i]][i]-=mn;
            flx[i][dad[i]]+=mn;
        }
        val=val+mn*sum;
    }
    g<<val;
    return 0;
}