#include <bits/stdc++.h>
#define pii pair<int, int>
#define inf 1000000000
///N=60
///cost=10000
using namespace std;
int n, m, i, j, k, s, d;
long long sol;
int flow[62][62], cost[62][62], dmin[62], then[62], now[62], last[62], gin[62], gout[62];
vector<int> graph[62];
priority_queue<pii, vector<pii>, greater<pii> > pq;
///
void read();
void solve();
void write();
bool bfs();
int main()
{
    read();
    solve();
    write();
    return 0;
}
void read(){
    freopen("traseu.in", "r", stdin);
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; ++i){
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        ++gin[y];
        ++gout[x];
        cost[x][y]=c;
        cost[y][x]=-c;
        flow[x][y]=inf;
        sol+=c;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    fclose(stdin);
    return;
}
void solve(){
    d=n+1;
    for(i=1; i<=n; ++i) {
        if(gin[i]<gout[i]) {
            flow[i][d]=gout[i]-gin[i];
            graph[d].push_back(i);
            graph[i].push_back(d);
        }
        else if(gin[i]>gout[i]){
            flow[s][i]=gin[i]-gout[i];
            graph[i].push_back(s);
            graph[s].push_back(i);
        }
    }
    while(bfs()){
        int p, maxflow=inf;
        for(p=d; p!=s; p=last[p]) maxflow=min(maxflow, flow[last[p]][p]);
        for(p=d; p!=s; p=last[p]){
            flow[last[p]][p]-=maxflow;
            flow[p][last[p]]+=maxflow;
            sol+=cost[last[p]][p]*maxflow;
        }
    }
    return;
}
void write(){
    freopen("traseu.out", "w", stdout);
    printf("%lld", sol);
    return;
}
bool bfs(){
    for(i=0; i<=n+1; ++i) last[i]=0, dmin[i]=inf;
    dmin[0]=now[0]=0;
    pq.push({0, s});
    while(!pq.empty()){
        int cst=pq.top().first, node=pq.top().second; pq.pop();
        if(node==d) continue;
        if(cst>dmin[node]) continue;
        for(auto next:graph[node]){
            if(!flow[node][next]) continue;
            int cnext=cst+cost[node][next]+then[node]-then[next];
            if(cnext<dmin[next]){
                dmin[next]=cnext;
                last[next]=node;
                now[next]=now[node]+cost[node][next];
                pq.push({dmin[next], next});
            }
        }
    }
    for(i=0; i<=n+1; ++i) then[i]=now[i];
    return dmin[d]!=inf;
}