#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("traseu.in");
ofstream fout("traseu.out");

const int N = 65;
const int INF = 1e9;

int n, m, fmax, costMin, gn;
int t[N], cap[N][N], cost[N][N], flow[N][N], gradInt[N], gradExt[N];
vector<int> dist;
vector<int> g[N];
vector<bool> vis;

vector<bool> inCoada;
void BellmanFordCoada(int startNode)
{
    inCoada.assign(gn, false);
    dist.assign(gn, INF);

    queue<int> coada;
    coada.push(startNode);
    inCoada[startNode] = true;
    dist[startNode] = 0;
    t[startNode] = 0;

    while(!coada.empty())
    {
        int x = coada.front();
        coada.pop();
        inCoada[x] = false;

        for (int y : g[x])
        {
            if (dist[x] + cost[x][y] < dist[y] && flow[x][y] != cap[x][y])
            {
                t[y] = x;
                dist[y] = dist[x] + cost[x][y];
                if (!inCoada[y])
                {
                    coada.push(y);
                    inCoada[y] = true;
                }
            }
        }
    }
}

void maxFlowMinCost(int source, int sink)
{
    do
    {
        BellmanFordCoada(source);

        if(dist[sink] == INF)
            break;

        int fmin = 1 << 30;
        for(int node = sink; node != source; node = t[node])
            fmin = min(fmin, cap[t[node]][node] - flow[t[node]][node]);

        fmax += fmin;
        costMin += dist[sink] * fmin;
        for(int node = sink; node != source; node = t[node])
        {
            flow[t[node]][node] += fmin;
            flow[node][t[node]] -= fmin;
        }
    } while(dist[sink] != INF);
}

void addEdge(int x, int y, int c, int z)
{
    g[x].push_back(y);
    g[y].push_back(x);
    cap[x][y] = c;
    cap[y][x] = 0;
    cost[x][y] = z;
    cost[y][x] = -z;
}

int main()
{
    fin >> n >> m;
    gn = n + 2;

    int ans = 0;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        ans += c;

        addEdge(x, y, INF, c);

        gradExt[x]++;
        gradInt[y]++;
    }
    
    for (int i = 1; i <= n; i++)
    {
        if (gradInt[i] > gradExt[i])
            addEdge(0, i, gradInt[i] - gradExt[i], 0);
        else if (gradInt[i] < gradExt[i])
            addEdge(i, n + 1, gradExt[i] - gradInt[i], 0);
    }

    maxFlowMinCost(0, n + 1);
    fout << ans + costMin << '\n';

    return 0;
}