#include <fstream>
#include <vector>
#include <queue>
#define NMAx 64
#define oo (1<<30)
#define pb push_back
using namespace std;

queue <short> Q;
vector <short> G[NMAx];
int Cost[NMAx][NMAx],Flux[NMAx][NMAx],dist[NMAx];
int IN[NMAx],OUT[NMAx],in_queue[NMAx],tata[NMAx];
int n,Flow,S,D,color;

bool BellmanFord() {

    int i,nod,vecin;

    for(i=S;i<=D;i++)
        dist[i]=oo;

    Q.push(S);
    dist[S]=0;
    color++;

    while(!Q.empty()) {

        nod=Q.front();
        Q.pop();
        in_queue[nod]=0;

        for(i=0;i<G[nod].size();i++) {
            vecin=G[nod][i];

            if(Flux[nod][vecin]>0&&dist[vecin]>dist[nod]+Cost[nod][vecin]) {

                dist[vecin]=dist[nod]+Cost[nod][vecin];
                tata[vecin]=nod;

                if(in_queue[vecin]!=color) {

                    in_queue[vecin]=color;
                    Q.push(vecin);
                    }
                }
            }
        }

    if(dist[D]==oo)
        return 0;
    return 1;

}
void constr_flux_network() {

    int i;

    S=0;
    D=n+1;

    for(i=1;i<=n;i++) {
        if(IN[i]>OUT[i]) {

            Flux[S][i]=IN[i]-OUT[i];
            G[S].pb(i);
            G[i].pb(S);
            }
        else
        if(OUT[i]>IN[i]) {

            Flux[i][D]=OUT[i]-IN[i];
            G[i].pb(D);
            G[D].pb(i);
            }
        }

}
void citire() {

    int i,x,y,c,m;
    ifstream in("traseu.in");
    in>>n>>m;

    for(i=0;i<m;i++) {
        in>>x>>y>>c;

        Cost[x][y]=c;
        Cost[y][x]=-c;

        G[x].pb(y);
        G[y].pb(x);

        IN[y]++;
        OUT[x]++;

        Flux[x][y]=oo;
        Flow+=c;

        }

    in.close();

}
int main() {

    int e,nod;
    citire();

    constr_flux_network();

    while(BellmanFord()) {

        e=oo;
        for(nod=D;nod!=S;nod=tata[nod])
            e=min(e,Flux[tata[nod]][nod]);

        for(nod=D;nod!=S;nod=tata[nod]) {

            Flux[tata[nod]][nod]-=e;
            Flux[nod][tata[nod]]+=e;
            }

        Flow+=e*dist[D];

        }

    ofstream out("traseu.out");
    out<<Flow<<'\n';
    out.close();

    return 0;
}