#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>
 
#define newn a[x][i]
 
using namespace std;
 
ifstream fin("traseu.in");
ofstream fout("traseu.out");
 
const int N = 65;
const int s = 0, d = 62;
const int oo = 0x3f3f3f3f;
 
int n, m, sol, dist[N], gin[N], gout[N], c[N][N], cst[N][N], f[N][N], t[N];
vector <bool> uz(N);
vector <int> a[N];
queue <int> q;
 
bool inline Bellman_Ford()
{
    memset(dist, oo, sizeof dist);
    uz.assign(N, 0); uz[s] = 1;
    for(dist[s] = 0, q.push(s); !q.empty(); q.pop())
    {
        int x = q.front();
        uz[x] = 0;
        for(unsigned i=0; i<a[x].size(); i++)
            if(f[x][newn] < c[x][newn] && dist[x] + cst[x][newn] < dist[newn])
            {
                t[newn] = x;
                dist[newn] = dist[x] + cst[x][newn];
                if(!uz[newn])
                {
                    q.push(newn);
                    uz[newn] = 1;
                }
            }
    }
    return (dist[d] != oo);
}
 
int main()
{
    fin>>n>>m;
    while(m--)
    {
        int x, y, z;
        fin>>x>>y>>z;
        a[x].push_back(y);
        a[y].push_back(x);
        sol += z;
        c[x][y] = oo;
        cst[x][y] = z;
        cst[y][x] = -z;
        gout[x]++; gin[y]++;
    }
 
    for(int i=1; i<=n; i++)
    {
        if(gin[i] > gout[i])
        {
            a[s].push_back(i);
            c[s][i] = gin[i] - gout[i];
        }
        else if(gout[i] > gin[i])
        {
            a[i].push_back(d);
            c[i][d] = gout[i] - gin[i];
        }
    }
 
    while(Bellman_Ford())
    {
        int fmin = oo;
        for(int j=d; j!=s; j=t[j])
            fmin = min(fmin, c[t[j]][j] - f[t[j]][j]);
        for(int j=d; j!=s; j=t[j])
        {
            f[t[j]][j] += fmin;
            f[j][t[j]] -= fmin;
        }
        sol += dist[d] * fmin;
    }
    fout<<sol;
    return 0;
}