#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>

using namespace std;

const int MaxN = 65;
const int oo = 100000000;

vector<int> G[MaxN];
int N, In[MaxN], Out[MaxN], Dist[MaxN], Father[MaxN], Sol;
bool InQ[MaxN];
queue<int> Q;
int S, D, Cost[MaxN][MaxN], Cap[MaxN][MaxN], Flow[MaxN][MaxN];

void RoyFloyd() {
    for (int k = 1; k <= N; ++k)
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                if (i != k && j != k && (Cost[i][j] == 0 || Cost[i][k]+Cost[k][j] < Cost[i][j]))
                    Cost[i][j] = Cost[i][k]+Cost[k][j];
}

void BuildGraph() {
    S = 0, D = N+1;
    for (int X = 1; X <= N; ++X) {
        if (In[X] > Out[X]) {
            G[S].push_back(X), G[X].push_back(S);
            Cap[S][X] = In[X]-Out[X];
        }
        if (Out[X] > In[X]) {
            G[X].push_back(D), G[D].push_back(X);
            Cap[X][D] = Out[X]-In[X];
        }
    }
    for (int X = 1; X <= N; ++X) {
        for (int Y = 1; Y <= N; ++Y) {
            if (In[X] > Out[X] && Out[Y] > In[Y]) {
                G[X].push_back(Y), G[Y].push_back(X);
                Cap[X][Y] = oo;
                Cost[Y][X] = -Cost[X][Y];
            }
        }
    }
}

void InitBF(int Start) {
    for (int X = S; X <= D; ++X)
        Dist[X] = oo, Father[X] = -1, InQ[X] = false;
    Dist[Start] = 0, Father[Start] = Start, Q.push(Start), InQ[Start] = true;
}

bool BellmanFord(int Start, int End) {
    for (InitBF(Start); !Q.empty(); Q.pop()) {
        int X = Q.front(); InQ[X] = false;
        for (vector<int>::iterator Y = G[X].begin(); Y != G[X].end(); ++Y) {
            if (Dist[X]+Cost[X][*Y] < Dist[*Y] && Cap[X][*Y] > Flow[X][*Y]) {
                Dist[*Y] = Dist[X]+Cost[X][*Y], Father[*Y] = X;
                if (!InQ[*Y])
                    Q.push(*Y), InQ[*Y] = true;
            }
        }
    }
    return Father[End] != -1;
}

void EdmondsKarp() {
    int MaxFlow = 0;
    for (int CFlow; BellmanFord(S, D); MaxFlow += CFlow) {
        CFlow = oo;
        for (int X = D; X != S; X = Father[X])
            CFlow = min(CFlow, Cap[Father[X]][X]-Flow[Father[X]][X]);
        for (int X = D; X != S; X = Father[X])
            Flow[Father[X]][X] += CFlow, Flow[X][Father[X]] -= CFlow;
        Sol += Dist[D]*CFlow;
    }
}

void Solve() {
    RoyFloyd();
    BuildGraph();
    EdmondsKarp();
}

void Read() {
    assert(freopen("traseu.in", "r", stdin));
    int M; assert(scanf("%d %d", &N, &M) == 2);
    for (; M; --M) {
        int X, Y, C; assert(scanf("%d %d %d", &X, &Y, &C) == 3);
        Cost[X][Y] = C; ++Out[X], ++In[Y];
        Sol += Cost[X][Y];
    }
}

void Print() {
    assert(freopen("traseu.out", "w", stdout));
    printf("%d\n", Sol);
}

int main() {
    Read();
    Solve();
    Print();
}