#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

typedef pair<int,int> PII;
const int NMAX = 60+5;
const int INF = (1<<30);
const int S = 0;
const int D = 61;

ifstream fin("traseu.in");
ofstream fout("traseu.out");

int N,M,solution;
vector<PII> V[NMAX];
priority_queue<PII,vector<PII>,greater<PII> > PQ;
int dist[NMAX];
int cost[NMAX][NMAX];
int capacity[NMAX][NMAX];
int flow[NMAX][NMAX];
int d[NMAX];
int father[NMAX];

bool bestPath()
{
    int i,x;
    vector<PII>::iterator it;

    for(i=1; i<=D; i++)
        dist[i]=INF;

    dist[S]=0;
    PQ.push(make_pair(0,S));

    while(!PQ.empty())
    {
        x=PQ.top().second;
        PQ.pop();

        for(it=V[x].begin(); it!=V[x].end(); it++)
            if(dist[x]+it->second < dist[it->first] && flow[x][it->first]<capacity[x][it->first])
            {
                dist[it->first]=dist[x]+it->second;
                father[it->first]=x;
                PQ.push(make_pair(dist[it->first],it->first));
            }
    }
    return (dist[D]!=INF);
}

int main()
{
    int x,y,i,c,v;

    fin>>N>>M;

    while(M--)
    {
        fin>>x>>y>>c;
        capacity[x][y]=INF;
        cost[x][y]=c;
        cost[y][x]=-c;
        V[x].push_back(make_pair(y,c));
        V[y].push_back(make_pair(x,-c));
        d[x]--;
        d[y]++;
        solution+=c;
    }

    for(i=1; i<=N; i++)
        if(d[i]>0)
        {
            capacity[S][i]=d[i];
            V[S].push_back(make_pair(i,0));
            V[i].push_back(make_pair(S,0));
        }
        else if(d[i]<0)
        {
            capacity[i][D]=-d[i];
            V[i].push_back(make_pair(D,0));
            V[D].push_back(make_pair(i,0));
        }

    while(bestPath())
    {
        v=INF;
        for(i=D; i; i=father[i])
            v=min(v,capacity[father[i]][i]-flow[father[i]][i]);
        for(i=D; i; i=father[i])
        {
            solution+=v*cost[father[i]][i];
            flow[father[i]][i]+=v;
            flow[i][father[i]]-=v;
        }
    }

    fout<<solution;

    return 0;
}