/**
  *  Worg
  */
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
FILE *fin = freopen("traseu.in", "r", stdin);
FILE *fout = freopen("traseu.out", "w", stdout);

const int MAX_N = 1 + 60 + 2;
const int MAX_INF = 0x3fffffff;

/*-----------------------------------*/
int N, M;
int inDegree[MAX_N], outDegree[MAX_N];
int dist[MAX_N][MAX_N];
/*-----------------------------------*/
vector< int > graph[MAX_N];
int cap[MAX_N][MAX_N], cost[MAX_N][MAX_N];

queue< int > Q;
bool inQueue[MAX_N];
int dmin[MAX_N], before[MAX_N];
/*-----------------------------------*/
int solDist;
/*-----------------------------------*/


void readData() {
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            dist[i][j] = MAX_INF;
        }
    }
    for(int i = 1; i <= M; i++) {
        int u, v, d; scanf("%d%d%d", &u, &v, &d);
        inDegree[v]++; outDegree[u]++; dist[u][v] = d; solDist += d;
    }
}

void royFloyd() {
    for(int k = 1; k <= N; k++) {
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(k != i && k != j) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

void constructGraph() {
    const int S = 0;
    const int D = N + 1;

    for(int i = 1; i <= N; i++) {
        if(inDegree[i] > outDegree[i]) {
            graph[S].push_back(i); graph[i].push_back(S);
            cap[S][i] = inDegree[i] - outDegree[i];
        }
    }
    for(int i = 1; i <= N; i++) {
        if(inDegree[i] > outDegree[i]) {
            for(int j = 1; j <= N; j++) {
                if(inDegree[j] < outDegree[j]) {
                    graph[i].push_back(j); graph[j].push_back(i);
                    cap[i][j] = MAX_INF;
                    cost[i][j] = dist[i][j]; cost[j][i] = -dist[i][j];
                }
            }
        }
    }
    for(int i = 1; i <= N; i++) {
        if(inDegree[i] < outDegree[i]) {
            graph[i].push_back(D); graph[D].push_back(i);
            cap[i][D] = outDegree[i] - inDegree[i];
        }
    }
}

bool bellmanFord() {
    const int S = 0;
    const int D = N + 1;

    for(int i = S; i <= D; i++) {
        dmin[i] = MAX_INF;
    }
    dmin[S] = 0; Q.push(S);

    while(!Q.empty()) {
        int node = Q.front(); Q.pop();
        for(vector< int >::iterator it = graph[node].begin(); it != graph[node].end(); it++) {
            if(cap[node][*it] && dmin[node] + cost[node][*it] < dmin[*it]) {
                dmin[*it] = dmin[node] + cost[node][*it];
                before[*it] = node;
                if(!inQueue[*it]) {
                    Q.push(*it); inQueue[*it] = true;
                }
            }
        }
    }

    if(dmin[D] == MAX_INF) {
        return false;
    } else {
        int flow = MAX_INF;
        for(int node = D; node != S; node = before[node]) {
            flow = min(flow, cap[before[node]][node]);
        }
        for(int node = D; node != S; node = before[node]) {
            solDist += cost[before[node]][node] * flow;
            cap[before[node]][node] -= flow;
            cap[node][before[node]] += flow;
        }

        return true;
    }
}

void writeData() {
    printf("%d", solDist);
}

int main() {
    readData();
    royFloyd();
    constructGraph();
    while(bellmanFord());
    writeData();
    return 0;
}