#include <fstream>
#include <queue>
#include <vector>
#define DIMN 100
#define INF 1000000000

using namespace std;

ifstream f("traseu.in");
ofstream g("traseu.out");

int grad[DIMN], v1[DIMN], v2[DIMN], C[DIMN][DIMN], F[DIMN][DIMN], T[DIMN], cost[DIMN][DIMN], D[DIMN][DIMN], d[DIMN];

bool viz[DIMN], ok;

queue<int> q;

vector<int> L[DIMN];

int n, m, x, y, z, n1, n2;

int BF () {
    for (int i=0; i<=n; ++i)
        viz[i] = 0, d[i] = INF;
    d[0] = 0;
    q.push(0);
    while ( !q.empty() ) {
        int nod = q.front(),vec;
        q.pop();
        viz[nod] = 0;
        for (vector<int>::iterator it=L[nod].begin(); it!=L[nod].end(); ++it) {
            vec = *it;
            if (C[nod][*it] - F[nod][*it] > 0 && d[*it] > d[nod] + cost[nod][*it]) {
                d[*it] = d[nod] + cost[nod][*it];
                T[*it] = nod;
                if (viz[*it])
                    continue;
                viz[*it] = 1;
                q.push(*it);
            }
        }
    }
    if (d[n] == INF)
        return 0;
    ok = 1;
    int Min = INF;
    for (int i=n; i!=0; i=T[i])
        Min = min(Min, C[T[i]][i] - F[T[i]][i]);
    for (int i=n; i!=0; i=T[i]) {
        F[T[i]][i] += Min;
        F[i][T[i]] -= Min;
    }
    return Min*d[n];
}

int main () {
    int ans = 0;
    f >> n >> m;
    for (int i=1; i<=m; ++i) {
        f >> x >> y >> z;
        L[x].push_back(y);
        L[y].push_back(x);
        C[x][y] = INF;
        cost[x][y] = z;
        cost[y][x] = -z;
        ans += z;
        --grad[x];
        ++grad[y];
    }
    for (int i=1; i<=n; ++i)
        if (grad[i] > 0)
            v1[++n1]=i;
        else
        if (grad[i] < 0)
            v2[++n2]=i;
    for (int i=1; i<=n1; ++i) {
        L[0].push_back(v1[i]);
        L[v1[i]].push_back(0);
        C[0][v1[i]] = grad[v1[i]];
    }
    ++n;
    for (int i=1; i<=n2; ++i) {
        L[n].push_back(v2[i]);
        L[v2[i]].push_back(n);
        C[v2[i]][n] = -grad[v2[i]];
    }
    ok = 1;
    while (ok) {
        ok = 0;
        ans += BF ();
    }
    g << ans;
    return 0;
}