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

#define MAX 65
#define INF 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

int N, M, S, D, totalCost;
int gIn[MAX], gOut[MAX], dist[MAX], dad[MAX];
int X[MAX][MAX], C[MAX][MAX], F[MAX][MAX];
bool inQueue[MAX];
vector< pair<int, int> > V[MAX];

void citire() {
    ifstream in("traseu.in");
    in>>N>>M;
    for(int i = 1, A, B, C; i <= M; i++) {
        in>>A>>B>>C;
        totalCost += C;
        X[A][B] = C;
        gOut[A]++;
        gIn[B]++;
    } in.close();
}

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 != j && i != k && j != k && X[i][k] + X[k][j] < X[i][j])
                    X[i][j] = X[i][k] + X[k][j];
}

void FormGraph() {
    S = 0; D = N + 1;
    for(int i = 1; i <= N; i++) {
        if(gIn[i] == gOut[i]) continue;
        if(gIn[i] > gOut[i]) {
            V[S].pb(mp(i, 0));
            V[i].pb(mp(S, 0));
            C[S][i] = gIn[i] - gOut[i];
            F[S][i] = 0;
            for(int j = 1; j <= N; j++)
                if(gIn[j] < gOut[j]) {
                    V[i].pb(mp(j, X[i][j]));
                    V[j].pb(mp(i, -X[i][j]));
                    C[i][j] = INF; F[i][j] = 0;
                }
        } else {
            V[i].pb(mp(D, 0));
            V[D].pb(mp(i, 0));
            C[i][D] = gOut[i] - gIn[i];
            F[i][D] = 0;
        }
    }
}

int BellmanFord() {
    memset(dist, INF, sizeof(dist));
    queue<int> Q;
    dist[S] = 0; Q.push(S); inQueue[S] = true;
    while(!Q.empty()) {
        int nod = Q.front(); Q.pop(); inQueue[nod] = false;
        for(size_t i = 0; i < V[nod].size(); i++) {
            int dest = V[nod][i].f, cost = V[nod][i].s;
            if(C[nod][dest] != F[nod][dest] && dist[dest] > dist[nod] + cost) {
                dist[dest] = dist[nod] + cost;
                dad[dest] = nod;
                if(!inQueue[dest]) {
                    Q.push(dest);
                    inQueue[dest] = true;
                }
            }
        }
    }
    if(dist[D] == INF) return -INF;
    int nod = D;
    while(nod != S) {
        F[dad[nod]][nod]++;
        F[nod][dad[nod]]--;
        nod = dad[nod];
    }
    return dist[D];
}

int Flux() {
    int add = 0, rez = 0;
    while((add = BellmanFord()) != -INF) {
        rez += add;
    }
    return rez;
}

int main() {
    memset(X, INF, sizeof(X));
    citire();
    RoyFloyd();
    FormGraph();
    totalCost += Flux();
    ofstream out("traseu.out"); out<<totalCost; out.close();
    return 0;
}