#include <bits/stdc++.h>

const int N = 65;
const int oo = 1e9;

using namespace std;

ifstream f("traseu.in") ;
ofstream g("traseu.out") ;

int n,m,i,x,y,z,ans,grad[N],cap[N][N],cost[N][N];
vector<int> v[N];

bool dij()
{
    priority_queue<pair<int,int> > Q;
    int dist[N],tata[N];
    for(i=0;i<=n+1;i++)
        dist[i]=oo,tata[i]=-1;
    dist[0]=0;Q.push({0,0});
    while(Q.size())
    {
        int x=Q.top().second,
          cst=Q.top().first;
        Q.pop();
        if(-cst!=dist[x])
            continue;
        for(auto it:v[x])
            if(cap[x][it]&&(dist[it]>dist[x]+cost[x][it]))
            {
                dist[it]=dist[x]+cost[x][it];
                Q.push({-dist[it],it});
                tata[it]=x;
            }
    }
    if(dist[n+1]==oo)
        return 0;
    int flux=oo,nod;
    for(nod=n+1;nod!=0;nod=tata[nod])
        flux=min(flux,cap[tata[nod]][nod]);
    for(nod=n+1;nod!=0;nod=tata[nod])
    {
        cap[tata[nod]][nod]-=flux;
        cap[nod][tata[nod]]+=flux;
    }
    ans+=flux*dist[n+1];
    return 1;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        v[x].push_back(y);
        v[y].push_back(x);
        cap[x][y]=N;
        cost[x][y]=z;
        cost[y][x]=-z;
        grad[x]--;
        grad[y]++;
        ans+=z;
    }
    for(i=1;i<=n;i++)
        if(grad[i]>0)
        {
            v[0].push_back(i);
            cap[0][i]=grad[i];
        }
        else
            if(grad[i]<0)
            {
                v[i].push_back(n+1);
                cap[i][n+1]=-grad[i];
            }
    for(;dij(););
    g<<ans;
}