#include <bits/stdc++.h>

using namespace std;

ifstream fin("traseu.in");
ofstream fout("traseu.out");

struct Edge {
    int to, rev, cap;
    long long cost;
};

const long long INF = 4e18;

int n, m, source, sink;
long long ans;
long long dist[65][65];
int in[65], out[65];

vector<vector<Edge>> G;
vector<long long> d;
vector<int> parentNode, parentEdge;

void addEdge(int x, int y, int cap, long long cost) {
    Edge a = {y, (int)G[y].size(), cap, cost};
    Edge b = {x, (int)G[x].size(), 0, -cost};

    G[x].push_back(a);
    G[y].push_back(b);
}

bool bellman() {
    queue<int> Q;
    vector<int> inQueue(sink + 1, 0);

    d.assign(sink + 1, INF);
    parentNode.assign(sink + 1, 0);
    parentEdge.assign(sink + 1, 0);

    d[source] = 0;
    Q.push(source);
    inQueue[source] = 1;

    while (!Q.empty()) {
        int node = Q.front();
        Q.pop();
        inQueue[node] = 0;

        for (int i = 0; i < (int)G[node].size(); ++i) {
            Edge edge = G[node][i];

            if (edge.cap > 0 && d[edge.to] > d[node] + edge.cost) {
                d[edge.to] = d[node] + edge.cost;
                parentNode[edge.to] = node;
                parentEdge[edge.to] = i;

                if (!inQueue[edge.to]) {
                    Q.push(edge.to);
                    inQueue[edge.to] = 1;
                }
            }
        }
    }

    return d[sink] != INF;
}

long long minCost() {
    long long cost = 0;

    while (bellman()) {
        int flow = 2e9;

        for (int node = sink; node != source; node = parentNode[node]) {
            int p = parentNode[node];
            int e = parentEdge[node];

            flow = min(flow, G[p][e].cap);
        }

        for (int node = sink; node != source; node = parentNode[node]) {
            int p = parentNode[node];
            int e = parentEdge[node];

            G[p][e].cap -= flow;
            G[node][G[p][e].rev].cap += flow;
        }

        cost += 1LL * flow * d[sink];
    }

    return cost;
}

int main() {
    fin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            dist[i][j] = INF;

        dist[i][i] = 0;
    }

    for (int i = 1; i <= m; ++i) {
        int x, y, c;
        fin >> x >> y >> c;

        ans += c;
        ++out[x];
        ++in[y];

        dist[x][y] = min(dist[x][y], 1LL * c);
    }

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

    source = 0;
    sink = 2 * n + 1;

    G.resize(sink + 1);

    for (int i = 1; i <= n; ++i) {
        if (in[i] > out[i])
            addEdge(source, i, in[i] - out[i], 0);

        if (out[i] > in[i])
            addEdge(n + i, sink, out[i] - in[i], 0);
    }

    for (int i = 1; i <= n; ++i) {
        if (in[i] > out[i]) {
            for (int j = 1; j <= n; ++j) {
                if (out[j] > in[j])
                    addEdge(i, n + j, 2e9, dist[i][j]);
            }
        }
    }

    fout << ans + minCost() << "\n";

    return 0;
}