// Flux maxim de cost minim
// Clasific nodurile in 3 categorii:
//  A. Nodurile cu gradul de intrare mai mare decat gradul de iesire
//  B. Nodurile cu gradul de intrare mai mic decat gradul de iesire
//  C. Nodurile cu gradul de intrare egal cu graul de iesire
// Leg toate nodurile B de destinatie cu capacitatea Gin - Gout
// Leg toate nodurile A de sursa cu capacitatea Gout - Gin
// Fac flux maxim de cost minim, si adun costul acestuia la suma totala initiala

#include <stdio.h>
#include <vector>
#include <algorithm>

#define nmax 65
#define inf 2000000000

using namespace std;

int n,m,i,j,n1,n2,cost,rez;
int Gin[nmax],Gout[nmax];
int cap[nmax][nmax],fl[nmax][nmax],Cost[nmax][nmax];

int d[nmax],prev[nmax];

int drum() {
    // gasesc un drum de inaintare de la sursa la destinatie
    // returnez 1 daca exista un drum de inaintare
    // returnez 0 daca nu

    int i,j,k;

    for(i = 0; i <= n + 1; i++) {
        d[i] = inf;
        prev[i] = -1;
    }
    d[0] = 0;

    for(i = 0; i <= n + 1; i++)
        for(j = 0; j <= n + 1; j++)
            for(k = 0; k <= n + 1; k++)
                if(d[j] != inf && cap[j][k] > fl[j][k]) {
                    int nd = d[j] + Cost[j][k];
                    if(nd < d[k]) {
                        d[k] = nd;
                        prev[k] = j;
                    }
                }

    if(d[n + 1] == inf) return 0;
    else {
        int minim = inf;
        int x = n + 1;
        while(x != 0) {
            minim = min(minim,cap[prev[x]][x] - fl[prev[x]][x]);
            x = prev[x];
        }
        x = n + 1;
        while(x != 0) {
            fl[prev[x]][x] += minim;
            fl[x][prev[x]] = -fl[prev[x]][x];
            x = prev[x];
        }
        return 1;
    }
}

int flux() {
    while(drum()) ;
    int r = 0;
    for(int i = 0; i <= n + 1; i++)
        for(int j = 0; j <= n + 1; j++)
            if(fl[i][j] > 0) r += fl[i][j] * Cost[i][j];
    return r;
}

int main() {
    freopen("traseu.in","r",stdin);
    freopen("traseu.out","w",stdout);

    scanf("%d%d",&n,&m);

    rez = 0;
    for(i = 1; i <= m; i++) {
        scanf("%d%d%d",&n1,&n2,&cost);
        rez += cost;
        Gout[n1]++; Gin[n2]++;
        Cost[n1][n2] = cost;
        Cost[n2][n1] = -cost;
        cap[n1][n2] = inf;
    }

    for(i = 1; i <= n; i++)
        if(Gin[i] < Gout[i]) cap[i][n + 1] = Gout[i] - Gin[i];
        else if(Gout[i] < Gin[i]) cap[0][i] = Gin[i] - Gout[i];

    rez += flux();

    printf("%d\n",rez);

    return 0;
}