#include <cstring>

#include <algorithm>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
const int MAX_N = 66;
const int INFINITE = 1000000000;

int rf[MAX_N][MAX_N];
int in[MAX_N], out[MAX_N];

vector<int> graph[MAX_N];
int n, cost[MAX_N][MAX_N];
int capacity[MAX_N][MAX_N];
bool in_queue[MAX_N];
int flow[MAX_N][MAX_N];
int father[MAX_N], dist[MAX_N];

int bellman_ford() {
    memset(in_queue, 0, sizeof in_queue);
    for(int i = 0; i <= n + 1; ++ i) {
        father[i] = -1;
        dist[i] = INFINITE;
    }
    queue<int> q;
    father[0] = -2; dist[0] = 0;
    q.push(0); in_queue[0] = true;
    while(!q.empty()) {
        int node = q.front();
        q.pop(); in_queue[node] = false;
        for(vector<int> :: iterator it = graph[node].begin(); it != graph[node].end(); ++ it) {
            if(flow[node][*it] < capacity[node][*it] && dist[*it] > dist[node] + cost[node][*it]) {
                dist[*it] = dist[node] + cost[node][*it];
                father[*it] = node;
                if(!in_queue[*it]) {
                    q.push(*it);
                }
            }
        }
    }
    if(dist[n + 1] == INFINITE) {
        return 0;
    }
    return 1;
}

int main() {
    ifstream fin("traseu.in");
    ofstream fout("traseu.out");
    int m, total_cost = 0;
    fin >> n >> m;
    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= n; ++ j) {
            rf[i][j] = INFINITE;
        }
    }
    for(int i = 1; i <= m; ++ i) {
        int x, y, z;
        fin >> x >> y >> z;
        rf[x][y] = z;
        total_cost += z;
        ++ 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) {
                rf[i][j] = min(rf[i][j], rf[i][k] + rf[k][j]);
            }
        }
    }
    for(int i = 1; i <= n; ++ i) {
        if(out[i] < in[i]) {
            graph[0].push_back(i);
            graph[i].push_back(0);
            capacity[0][i] = in[i] - out[i];
        }
    }
    for(int i = 1; i <= n; ++ i) {
        if(out[i] > in[i]) {
            graph[i].push_back(n + 1);
            graph[n + 1].push_back(i);
            capacity[i][n + 1] = out[i] - in[i];
        }
    }
    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= n; ++ j) {
            if(out[i] < in[i] && out[j] > in[j]) {
                graph[i].push_back(j);
                graph[j].push_back(i);
                capacity[i][j] = INFINITE;
                cost[i][j] = rf[i][j];
                cost[j][i] = -rf[i][j];
            }
        }
    }
    while(bellman_ford()) {
        int min_flow = capacity[father[n + 1]][n + 1] - flow[father[n + 1]][n + 1];
        for(int node = father[n + 1]; node; node = father[node]) {
            min_flow = min(min_flow, capacity[father[node]][node] - flow[father[node]][node]);
        }
        for(int node = n + 1; node; node = father[node]) {
            flow[father[node]][node] += min_flow;
            flow[node][father[node]] -= min_flow;
        }
        total_cost += min_flow * dist[n + 1];
    }
    fout << total_cost << "\n";
    return 0;
}