#include <bits/stdc++.h>
using namespace std;

//Constants
const int INF = (1<<30);
const long long MOD = 1e9 + 7;
const long double PI = 3.141592653589793;

//MACROS
#define pb push_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
typedef long long LL;
typedef pair <int,int> PII;

vector<int> g[100];
int cost[100][100], cap[100][100], n, m;
int e[100], t, s, dist[100], pr[100], cnt;
LL ans;

bool bf() {
    rep(i,0,100) dist[i] = INF, pr[i] = -1;
    dist[t] = 0;
    rep(i,1,n+2) rep(u,1,n+3) for (auto v : g[u])
        if (cap[u][v] && dist[u] + cost[u][v] < dist[v]) {
            dist[v] = dist[u] + cost[u][v];
            pr[v] = u;
        }
    return dist[s] < INF;
}

void pushflow() {
    cnt++;
    int cur = s, flow = INF;
    while (cur != t) flow = min(flow,cap[pr[cur]][cur]), cur = pr[cur];
    cur = s;
    while (cur != t) {
        ans += 1LL * cost[pr[cur]][cur] * flow;
        cap[pr[cur]][cur] -= flow;
        cap[cur][pr[cur]] += flow;
        cur = pr[cur];
    }
}

int main() {
	freopen("traseu.in","r",stdin);
	freopen("traseu.out","w",stdout);
	cin >> n >> m;
	rep(i,0,m) {
	    int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        ans += w;
        g[u].pb(v);
        g[v].pb(u);
        e[u]++, e[v]--;
        cost[u][v] = w, cost[v][u] = -w;
        cap[u][v] = INF, cap[v][u] = 0;
	}
	t = n + 1, s = n + 2;
	rep(i,0,n) {
	    if (e[i] == 0) continue;
        if (e[i] < 0) {
            g[t].pb(i);
            g[i].pb(t);
            cap[t][i] = -e[i];
        } else {
            g[i].pb(s);
            g[s].pb(i);
            cap[i][s] = e[i];
        }
	}
    while (bf()) pushflow();
    cout << ans;
}