#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
const int inf=1e9;
using namespace std;
ifstream si("traseu.in");
ofstream so("traseu.out");
int n, m, x, y, z, ans, grad[65], cap[65][65], cost[65][65];
vector<int> v[65];
bool dij() {
    queue<int> q;
    int dist[65], tata[65];
    for(int i=0; i<=n+1; i++) {
        dist[i]=inf;
        tata[i]=-1;
    }
    dist[0]=0;
    q.push(0);
    while(q.size()) {
        int x=q.front();
        q.pop();
        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(it);
                tata[it]=x;
            }
    }
    if(dist[n+1]==inf)
        return 0;
    int flux=inf, 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()
{
    si>>n>>m;
    for(int i=1; i<=m; i++) {
        si>>x>>y>>z;
        v[x].push_back(y);
        v[y].push_back(x);
        cap[x][y]=65;
        cost[x][y]=z;
        cost[y][x]=-z;
        grad[x]--;
        grad[y]++;
        ans+=z;
    }
    for(int 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(););
    so<<ans;
    return 0;
}