#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define pb push_back
#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

constexpr int V = 2007;
constexpr int E = 100007;

inline bool getmin(int &a, int b) {return (a > b ? (a = b, true) : false);}

int tot = 1, S, T, hd[V];

struct edge{int nxt, to, cap, cst;} e[E << 1];

void clear() {tot = 1; memset(hd, 0, sizeof(hd));}

void add(int u, int v, int cap, int cst) {
    e[++tot] = {hd[u], v, cap, cst}; hd[u] = tot;
    e[++tot] = {hd[v], u, 0,  -cst}; hd[v] = tot;
}

int inid[V], fl[V], dis[V];

inline bool spfa() {
    static queue<int> q;
    static bool inq[V];
    memset(inq, 0, sizeof(inq));
    memset(dis, 0x3f, sizeof(dis));
    int cstInf = dis[0];

    q.push(S); dis[S] = 0; fl[S] = INT_MAX;
    while (!q.empty()) {
        int u = q.front();
        q.pop(); inq[u] = false;
        for (int i = hd[u], v; i; i = e[i].nxt)
            if (e[i].cap != 0 && getmin(dis[v = e[i].to], dis[u] + e[i].cst)) {
                inid[v] = i;
                fl[v] = min(e[i].cap, fl[u]);
                if (!inq[v]) {inq[v] = true; q.push(v);}
            }
    }
    return dis[T] < cstInf;
}

pair<int, int> EK() {
    int flow = 0;
    int cost = 0;
    while (spfa()) {
        flow += fl[T];
        cost += dis[T] * fl[T];
        for (int u = T; u != S; u = e[inid[u] ^ 1].to)
            e[inid[u]].cap -= fl[T], e[inid[u] ^ 1].cap += fl[T];
    }
    return make_pair(flow, cost);
}

int n, m;

inline void work() {
    clear();
    S = 0; T = 2 * n - 1;
    add(S, 2, 2, 0);
    rep(i, 1, n) add(i * 2 - 1, i * 2, 1, 0);
    rep(i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u * 2, v * 2 - 1, 1, w);
    }
    auto [flow, cost] = EK();
    printf("%d\n", cost);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (cin >> n >> m) work();
    return 0;
}