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

#define FILEIN "traseu.in"
#define FILEOUT "traseu.out"
#define NMAX 64

using namespace std;

int n, m;
vector<pair<int, int> > A[NMAX];
int Out[NMAX], In[NMAX];

const int INF = 0x3F3F3F3F;
const int SRC = 0;
const int DST = 61;
vector<int> B[NMAX];
int Flux[NMAX][NMAX];
int Cost[NMAX][NMAX];
int Cap[NMAX][NMAX];
int D[NMAX];
int T[NMAX];

void distances(int i) {
    memset(D, INF, sizeof(D));

    queue<int> Q;
    Q.push(i);
    D[i] = 0;

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for (int i = 0; i < A[x].size(); i++) {
            int y = A[x][i].first;

            if (D[y] > D[x] + A[x][i].second) {
                D[y] = D[x] + A[x][i].second;
                Q.push(y);
            }
        }
    }
}

long long bellman(bool& road) {
    bool Uz[NMAX];

    memset(D, INF, sizeof(D));
    memset(Uz, 0, sizeof(Uz));

    for (int i = 0; i <= n+1; i++) {
        T[i] = -1;
    }

    queue<int> Q;
    Q.push(SRC);
    D[SRC] = 0;
    Uz[SRC] = 1;
    while (!Q.empty()) {
        int x = Q.front();
        Uz[x] = 0;
        Q.pop();

        for (int i = 0; i < B[x].size(); i++) {
            int y = B[x][i];

            if (Cap[x][y] > Flux[x][y] && D[x] + Cost[x][y] < D[y]) {
                D[y] = D[x] + Cost[x][y];
                T[y] = x;
                if (!Uz[y]) {
                    Q.push(y);
                    Uz[y] = 1;
                }
            }
        }
    }

    if (D[DST] == INF) {
        road = false;
        return 0;
    } else {
        road = true;
        int fmin = INF;

        for (int i = DST; i != SRC; i = T[i]) {
            fmin = min(fmin, Cap[T[i]][i] - Flux[T[i]][i]);
        }

        for (int i = DST; i != SRC; i = T[i]) {
            Flux[T[i]][i] += fmin;
            Flux[i][T[i]] -= fmin;
        }

        return 1LL * fmin * D[DST];
    }
}

long long flux(long long ans) {
    bool road = 1;
    while (road) {
        ans += bellman(road);
    }

    return ans;
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    cin >> n >> m;

    long long ans = 0;

    for (int i = 1, x, y, z; i <= m; i++) {
        cin >> x >> y >> z;

        ans += z;
        A[x].push_back(make_pair(y, z));
        Out[x]++;
        In[y]++;
    }

    for (int i = 1; i <= n; i++) {
        if (In[i] > Out[i]) {
            Cost[SRC][i] = Cost[i][SRC] = 0;
            Cap[SRC][i] = In[i] - Out[i];

            B[i].push_back(SRC);
            B[SRC].push_back(i);
        }
        if (In[i] < Out[i]) {
            Cost[i][DST] = Cost[DST][i] = 0;
            Cap[i][DST] = Out[i] - In[i];

            B[i].push_back(DST);
            B[DST].push_back(i);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (In[i] <= Out[i])
            continue;
        distances(i);
        for (int j = 1; j <= n; j++) {
            if (In[j] >= Out[j])
                continue;
            B[i].push_back(j);
            B[j].push_back(i);

            Cost[i][j] = D[j];
            Cost[j][i] = -D[j];
            Cap[i][j] = INF;
        }
    }

    cout << flux(ans) << '\n';

    return 0;
}