#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

#define ITERATOR vector <int>::iterator
const int NMAX = 65, INF = 2e9;

int n, SOURCE, DEST;
int in[NMAX], out[NMAX], cap[NMAX][NMAX], flow[NMAX][NMAX], dad[NMAX], cost[NMAX][NMAX], dmin[NMAX];
bool vis[NMAX];
vector <int> graph[NMAX];

void royFloyd() {
    int i, j, k;

    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= n; ++ j)
            if(!cost[i][j])
                cost[i][j] = INF;

    for(k = 1; k <= n; ++ k)
        for(i = 1; i <= n; ++ i)
            for(j = 1; j <= n; ++ j)
                if(k != i && k != j && i != j && cost[i][k] != INF && cost[k][j] != INF)
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
}

void drawEdge (int a, int b, int capAB, int costAB) {
    graph[a].push_back(b);
    graph[b].push_back(a);

    cap[a][b] = capAB;

    cost[a][b] = costAB;
    cost[b][a] = -costAB;
}

bool bellmanFord () {
    int i, node;
    queue <int> q; 

    for(i = SOURCE; i <= DEST; ++ i) {
        dmin[i] = INF;
        dad[i] = vis[i] = 0;
    }

    q.push(SOURCE);
    vis[SOURCE] = 1;
    dmin[SOURCE] = 0;
    while(!q.empty()) {
        node = q.front();
        vis[node] = 0;
        q.pop();
        if(node == DEST)
            continue;

        for(ITERATOR it = graph[node].begin(); it != graph[node].end(); ++ it) 
            if(flow[node][*it] < cap[node][*it] && dmin[node] + cost[node][*it] < dmin[*it]) {
                dmin[*it] = dmin[node] + cost[node][*it];
                dad[*it] = node;

                if(!vis[*it]) {
                    vis[*it] = 1;
                    q.push(*it);
                }
            }
    }

    if(dmin[DEST] != INF)
        return 1;
    return 0;
}

int maxFlow() {
    int node, res, minFlow;
    
    res = 0;
    while(bellmanFord()) {
        node = DEST;
        minFlow = INF;
        while(node != SOURCE) {
            minFlow = cap[dad[node]][node] - flow[dad[node]][node];
            node = dad[node];
        }

        node = DEST;
        while(node != SOURCE) {
            flow[dad[node]][node] += minFlow;
            flow[node][dad[node]] -= minFlow;
            node = dad[node];
        }

        res += dmin[DEST] * minFlow;
    }

    return res;
}

int main() {
    freopen("traseu.in", "r", stdin);
    freopen("traseu.out", "w", stdout);
    int m, i, j, x, y, ans;

    scanf("%d%d", &n, &m);
    ans = 0;
    for(i = 1; i <= m; ++ i) {
        scanf("%d%d", &x, &y);
        scanf("%d", &cost[x][y]);

        ++ out[x];
        ++ in[y];
        ans += cost[x][y];
    }


    royFloyd();

    SOURCE = 0;
    DEST = n + 1;
    
    for(i = 1; i <= n; ++ i)
        if(in[i] > out[i])
            drawEdge(SOURCE, i, in[i] - out[i], 0);

    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= n; ++ j)
            if(cost[i][j] != INF && in[i] > out[i] && in[j] < out[j])
                drawEdge(i, j, INF, cost[i][j]);

    for(i = 1; i <= n; ++ i)
        if(in[i] < out[i])
            drawEdge(i, DEST, out[i] - in[i], 0);

    ans += maxFlow();

    printf("%d\n", ans);
    return 0;
}