#include <bits/stdc++.h>

using namespace std;

FILE *F=fopen("traseu.in", "r"), *G=fopen("traseu.out", "w");

int n, s, d, x, y, z, m, ok, ans, dist[152], t[152], c[152][152], C[152][152], f[152][152], in[152], out[152];
vector<int> a[152];
bitset<152> inq;
queue<int> q;
const int inf = 2000000000;

int bellman()
{
    vector<int> :: iterator it;
    for(int i = s; i <= d; ++ i) dist[i] = inf, t[i] = 0;
    q.push(s); inq[s] = 1; dist[s] = 0;
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        inq[x] = 0;
        for(it = a[x].begin(); it != a[x].end(); ++ it)
        {
            y = *it;
            if(C[x][y] > f[x][y] && dist[y] > dist[x] + c[x][y])
            {
                dist[y] = dist[x] + c[x][y];t[y] = x;
                if(!inq[y]) inq[y] = 1, q.push(y);
            }
        }
    }
    if(dist[d] == inf) return 0;
    for(int i = d; i != s; i = t[i])
        f[t[i]][i]++, f[i][t[i]] --;
    return dist[d];
}

int main()
{
    fscanf(F, "%d %d ", &n, &m);
    for(int i = 0; i < m; ++ i)
    {
        fscanf(F, "%d %d %d ", &x, &y, &z);
        a[x].push_back(y);
        c[x][y] = z;
        a[y].push_back(x);
        c[y][x] = -z;
        C[x][y] = inf;
        ans += z;
        in[y] ++;
        out[x] ++;
    }
    s = 0; d = n+1;
    for(int i = 1; i <= n; ++ i)
    {
        if(in[i] > out[i])
        {a[i].push_back(s);
        a[s].push_back(i);
        c[s][i] = 0;
        c[i][s] = 0;
        C[s][i] = in[i] - out[i];}
        else
        {
            a[i].push_back(d);
        a[d].push_back(i);
        c[d][i] = 0;
        c[i][d] = 0;
        C[i][d] = out[i]-in[i];
        }
    }
    ok = 1;
    while(ok)
        ok = bellman(), ans += ok;
    fprintf(G, "%d", ans);
    return 0;
}