#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

const string file = "traseu";
const ll INF = 9223372036854775807ll;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, inf = 2147483647, nmax = 355;

int n, m, c[nmax][nmax], f[nmax][nmax], e[nmax][nmax], prv[nmax], old[nmax], d[nmax], trued[nmax], Entry, Exit, indegree[nmax], outdegree[nmax];
vector<int> v[nmax];
bool inq[nmax];

void bell()
{
    queue<int> q;
    q.push(Entry);
    memset(inq, 0, sizeof(inq));
    for (int i = 1; i <= n; ++i)
        old[i] = inf;
    old[Entry] = 0;
    while(!q.empty()){
        int k = q.front();
        q.pop();
        inq[k] = 0;
        for (auto x : v[k])
            if(c[k][x] && old[k]+e[k][x] < old[x]){
                old[x] = old[k]+e[k][x];
                if(!inq[x])
                    q.push(x);
                inq[x] = 1;
            }
    }
}

int dijkstra()
{
    priority_queue<pi> q;
    q.push({0, Entry});
    for (int i = 1; i <= n; ++i)
        d[i] = inf,
        trued[i] = inf;
    d[Entry] = 0;
    trued[Entry] = 0;
    while(!q.empty()){
        int k = q.top().ss, w = q.top().ff;
        q.pop();
        if(d[k] != -w)
            continue;
        for (auto x : v[k])
            if(f[k][x] < c[k][x] && old[k]-old[x]+d[k]+e[k][x] < d[x]){
                d[x] = old[k]-old[x]+d[k]+e[k][x];
                trued[x] = trued[k]+e[k][x];
                q.push({-d[x], x});
                prv[x] = k;
            }
    }
    for (int i = 1; i <= n; ++i)
        old[i] = trued[i];
    return trued[Exit];
}

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> n >> m;
    int cost = 0;
    for (int i = 1; i <= m; ++i){
        int x, y, z1, z2;
        z1 = inf;
        fin >> x >> y >> z2;
        ++indegree[y];
        ++outdegree[x];
        cost += z2;
        v[x].push_back(y);
        v[y].push_back(x);
        c[x][y] = z1;
        e[x][y] = z2;
        e[y][x] = -z2;
    }
    Entry = n+1;
    Exit = n+2;
    for (int i = 1; i <= n; ++i)
        if (indegree[i] > outdegree[i]){
            v[Entry].push_back(i);
            v[i].push_back(Entry);
            c[Entry][i] = indegree[i]-outdegree[i];
        }else if (indegree[i] < outdegree[i]){
            v[i].push_back(Exit);
            v[Exit].push_back(i);
            c[i][Exit] = outdegree[i]-indegree[i];
        }
    n += 2;
    bell();
    int flow = 0, add;
    while((add = dijkstra()) != inf){
        int now = Exit, mn = inf;
        while(now != Entry){
            mn = min(mn, c[prv[now]][now]-f[prv[now]][now]);
            now = prv[now];
        }
        flow += mn;
        cost += add*mn;
        now = Exit;
        while(now != Entry){
            f[prv[now]][now] += mn;
            f[now][prv[now]] -= mn;
            now = prv[now];
        }
    }
    fout << cost << "\n";
    return 0;
}