#include <stdio.h>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

const int NMAX = 100;

int f[NMAX][NMAX], cap[NMAX][NMAX], cost[NMAX][NMAX];
int dist[NMAX], father[NMAX];
vector <int> G[NMAX];
queue <int> Q;
bool inQ[NMAX];
int adj[NMAX][NMAX], degree[NMAX];

struct MaxFlowMinCost {
    long long maxFlow, minCost;
    int source, sink, N;

    void init(int S, int T, int n) {
        maxFlow = minCost = 0;
        source = S; sink = T; N = n;
    }

    void addEdge(int x0, int y0, int edgeCap, int edgeCost) {
        cap[x0][y0] = edgeCap;
        cost[x0][y0] = edgeCost;
        cost[y0][x0] = -edgeCost;
        G[x0].push_back(y0);
        G[y0].push_back(x0);
    }

    void initBellmanFord() {
        int i;
        for (i = 0; i <= sink; ++i)
            dist[i] = 1 << 30;
        dist[source] = 0; Q.push(source);
    }

    bool BellmanFord() {
        initBellmanFord();
        while (!Q.empty()) {
            int nod = Q.front();
            vector <int> :: iterator it;
            for (it = G[nod].begin(); it != G[nod].end(); ++it)
                if (f[nod][*it] < cap[nod][*it])
                    if (dist[*it] > dist[nod] + cost[nod][*it]) {
                        dist[*it] = dist[nod] + cost[nod][*it];
                        father[*it] = nod;
                        if (!inQ[*it]) {
                            inQ[*it] = true;
                            Q.push(*it);
                        }
                    }
            Q.pop(); inQ[nod] = false;
        }
        return dist[sink] != 1 << 30;
    }

    void augment() {
        int nod = sink, fmin = 1 << 30;
        while (nod != source) {
                if (fmin > cap[father[nod]][nod] - f[father[nod]][nod])
                    fmin = cap[father[nod]][nod] - f[father[nod]][nod];
                nod = father[nod];
            }
        nod = sink;
        while (nod != source) {
            f[father[nod]][nod] += fmin;
            f[nod][father[nod]] -= fmin;
            nod = father[nod];
        }
        minCost += dist[sink] * fmin;
        maxFlow += fmin;
    }

    void solve() {
        while (BellmanFord())
            augment();
    }

};

int main() {
    freopen("traseu.in", "r", stdin);
    freopen("traseu.out", "w", stdout);

    int N, M;
    scanf("%d%d", &N, &M);
    MaxFlowMinCost network;
    network.init(0, N + 1, N);

    long long res = 0;

    for (int i = 1; i <= M; ++i) {
        int xx, yy, cst;
        scanf("%d%d%d", &xx, &yy, &cst);
        --degree[xx]; ++degree[yy];
        adj[xx][yy] = cst;
        res += cst;
    }

    for (int i = 1; i <= N; ++i) {
        if (degree[i] > 0)
            network.addEdge(0, i, degree[i], 0);
        if (degree[i] < 0)
            network.addEdge(i, N + 1, -degree[i], 0);
    }

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if (adj[i][j] == 0 && i != j)
                adj[i][j] = 100000;

    for (int k = 1; k <= N; ++k)
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                if (adj[i][j] > adj[i][k] + adj[k][j])
                    adj[i][j] = adj[i][k] + adj[k][j];

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if (degree[i] > 0 && degree[j] < 0)
                network.addEdge(i, j, 1 << 30, adj[i][j]);

    network.solve();
    res += network.minCost;
    printf("%lld", res);
    return 0;
}