#include <bits/stdc++.h>
#define maxN 64
#define INF (1<<30)
using namespace std;
bool seen[maxN];
queue<int> Que;
int grad[maxN];
vector<int>v[maxN];
int n,m,i,j,x,y,z,dist[maxN],t[maxN];
int cost[maxN][maxN],cap[maxN][maxN],flow[maxN][maxN];
int nod,addflow,sol,maxflow,source,sink;
bool bellmanford()
{
    for(i=0;i<=n+1;i++)
        dist[i]=INF;
    memset(t,0,sizeof(t));
    memset(seen,false,sizeof(seen));
    Que.push(source);
    dist[source]=0;
    seen[source]=true;
    while(!Que.empty())
    {
        int nod=Que.front();
        Que.pop();
        for(vector<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
            if(cap[nod][*it]!=flow[nod][*it] && dist[nod]+cost[nod][*it]<dist[*it])
            {
                dist[*it]=dist[nod]+cost[nod][*it];
                t[*it]=nod;
                if(!seen[*it])
                    seen[*it]=true,
                    Que.push(*it);
            }
        seen[nod]=false;
    }
    if(dist[sink]==INF)
        return false;
    return true;
}
int main()
{
    freopen("traseu.in","r",stdin);
    freopen("traseu.out","w",stdout);
    scanf("%d %d",&n,&m);
    source=0,sink=n+1;
    for(i=1;i<=m;i++)
        scanf("%d %d %d",&x,&y,&z),
        v[x].push_back(y),
        v[y].push_back(x),
        cap[x][y]=INF,
        cost[x][y]=z,cost[y][x]=-z,
        grad[x]++,grad[y]--,
        sol+=z;
    for(i=1;i<=n;i++)
        if(grad[i]<0)
            v[source].push_back(i),
            v[i].push_back(source),
            cap[source][i]=-grad[i];
        else if(grad[i]>0)
            v[sink].push_back(i),
            v[i].push_back(sink),
            cap[i][sink]=grad[i];
    while(bellmanford())
    {
        addflow=INF;
        for(nod=sink;nod!=source;nod=t[nod])
            if(addflow>cap[t[nod]][nod]-flow[t[nod]][nod])
                addflow=cap[t[nod]][nod]-flow[t[nod]][nod];
        for(nod=sink;nod!=source;nod=t[nod])
            flow[t[nod]][nod]+=addflow,
            flow[nod][t[nod]]-=addflow;
        sol+=addflow*dist[sink];
    }
    printf("%d",sol);
    return 0;
}