# include <cstdio>
# include <cstring>
# include <deque>
# include <vector>
using namespace std;

const char *FIN = "traseu.in", *FOU = "traseu.out";
const int MAX = 62;

vector <int> G[MAX];
int N, M, sol, in[MAX], out[MAX], T[MAX], X[MAX], C[MAX][MAX], F[MAX][MAX], P[MAX][MAX];

inline void add (int x, int y) {
    G[x].push_back (y);
    G[y].push_back (x);
}

bool bellman (int S, int D) {
    deque <int> Q;
    int V[MAX];
    memset (X, 0, sizeof (X)), memset (V, 1, sizeof (V));
    T[D] = V[S] = 0, X[S] = MAX;
    for (Q.push_back (S); !Q.empty (); Q.pop_front ()) {
        int act = Q.front ();
        for (vector <int> :: iterator it = G[act].begin (); it != G[act].end (); ++it) {
            if (C[act][*it] - F[act][*it] > 0 && V[*it] > V[act] + P[act][*it]) {
                V[*it] = V[act] + P[act][*it];
                X[*it] = min (X[act], C[act][*it] - F[act][*it]);
                T[*it] = act, Q.push_back (*it);
            }
        }
    }
    if (X[D] == 0) return 0;
    for (int i = D; i != S; i = T[i]) {
        F[T[i]][i] += X[D];
        F[i][T[i]] -= X[D];
    }
    return 1;
}

inline void getmin (int &a, int b) {
    a = a < b ? a : b;
}

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d %d", &N, &M);
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if (i != j) P[i][j] = 0x3f3f3f3f;
    for (int i = 1, x, y, z; i <= M; ++i) {
        scanf ("%d %d %d", &x, &y, &z);
        P[x][y] = z, sol += P[x][y];
        ++out[x], ++in[y];
    }
    for (int k = 1; k <= N; ++k)
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                getmin (P[i][j], P[i][k] + P[k][j]);
    for (int i = 1; i <= N; ++i) {
        if (in[i] - out[i] == 0) continue;
        X[i] = (in[i] - out[i] > 0 ? -1 : +1);
        if (X[i] == -1)
            add (0, i), C[0][i] = in[i] - out[i];
        else if (X[i] == +1)
            add (i, N + 1), C[i][N + 1] = out[i] - in[i];
    }
    for (int i = 1; i <= N; ++i) {
        if (X[i] != -1) continue;
        for (int j = 1; j <= N; ++j)
            if (X[j] == +1) {
                P[j][i] = -P[i][j];
                add (i, j), C[i][j] = MAX;
            }
    }
    for (; bellman (0, N + 1) ;);
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if (F[i][j] > 0)
                sol += F[i][j] * P[i][j];
    fprintf (fopen (FOU, "w"), "%d", sol);
}