#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <complex>

using namespace std;
using ll = long long;
using R = double;
using P = pair<int, int>;

/**
 * Primal-Dual????????????????°??????¨???
 * ?????????????????´??°??§????????¨?§£??????????????¨?????¨???
 */
template<int V>
struct MinCostFlow {
    using C = ll;
    const C EPS = 0;
    using T = ll; /// ?????????????????????
    const T INF = 1LL<<55;
    using P = pair<T, int>;
    struct Edge {
        int to, rev;
        C cap;
        T cost;
    };
    vector<Edge> g[V];
    T h[V], dist[V];
    int pv[V], pe[V];
    void init() {
        for (int i = 0; i < V; i++) {
            g[i].clear();
        }
    }
    /// ????????????
    void add(int from, int to, C cap, T cost) {
        g[from].push_back(Edge{to, (int)g[to].size(), cap, cost});
        g[to].push_back(Edge{from, (int)g[from].size()-1, 0, -cost});
    }
    /**
     * ????°??????¨???????¨??????????
     *
     * bell?????¢?????????????????????????????¨????????´????????????????????°????????§????§£??????????????¨?????¨???
     *
     * Params:
     *   s = ?§????
     *   t = ??????
     *   f = ?????????
     *   bell = ?????????????????????????????¨??????????????????
     */
    T exec(int s, int t, C f, bool bell = false) {
        T res = 0;
        fill_n(h, V, 0);
        while (f > EPS) {
            fill_n(dist, V, INF);
            dist[s] = 0;
            if (bell) {
                bell = false;
                bool update;
                do {
                    update = false;
                    for (int v = 0; v < V; v++) {
                        if (dist[v] == INF) continue;
                        for (int i = 0; i < (int)g[v].size(); i++) {
                            Edge &e = g[v][i];
                            if (e.cap > EPS && dist[e.to] > dist[v] + e.cost) {
                                dist[e.to] = dist[v] + e.cost;
                                pv[e.to] = v;
                                pe[e.to] = i;
                                update = true;
                            }
                        }
                    }
                } while (update);
            } else {
                priority_queue<P, vector<P>, greater<P>> que;
                que.push(P(0, s));
                while (!que.empty()) {
                    P p = que.top(); que.pop();
                    int v = p.second;
                    if (dist[v] < p.first) continue;
                    for (int i = 0; i < (int)g[v].size(); i++) {
                        Edge &e = g[v][i];
                        if (e.cap > EPS && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                            dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                            pv[e.to] = v;
                            pe[e.to] = i;
                            que.push(P(dist[e.to], e.to));
                        }
                    }
                }
            }
            if (dist[t] == INF) {
                return INF;
            }
            for (int v = 0; v < V; v++) {
                h[v] += dist[v];
            }

            T d = f;
            for (int v = t; v != s; v = pv[v]) {
                d = min(d, g[pv[v]][pe[v]].cap);
            }
            f -= d;
            if (h[t] > 0) break;
            res += d * h[t];
            for (int v = t; v != s; v = pv[v]) {
                Edge &e = g[pv[v]][pe[v]];
                e.cap -= d;
                g[v][e.rev].cap += d;
            }
        }
        return res;
    }
};


const int MN = 110;
const int MM = 1100;

MinCostFlow<MN> mf;

int n, m;
int x[MM], y[MM]; ll s[MM];

int main() {
    static vector<P> g[MN];
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x[i] >> y[i] >> s[i];
        g[x[i]].push_back(P(y[i], s[i]));
    }
    static ll dis[MN];
    dis[n-1] = 0;
    for (int i = n-2; i >= 0; i--) {
        dis[i] = 0;
        for (P p: g[i]) {
            dis[i] = max(dis[i], dis[p.first] + p.second);
        }
    }
    ll X = dis[0];

    const ll INF = 1LL<<30;
    for (int i = 0; i < m; i++) {
        mf.add(x[i], y[i], 1, -s[i]-INF);
        mf.add(x[i], y[i], INF, -s[i]);
    }
    mf.add(n, 0, INF, X);

    cout << m * INF + mf.exec(n, n-1, INF, true) << endl;
    return 0;
}

Measured memory_bytes: 3256