#include <bits/stdc++.h>

using namespace std;

#define int long long
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define bitcnt __builtin_popcount
#define SZ(x) ((ll)(x).size())
#define fi first
#define se second
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define DCIN(...)                                                              \
    double __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"
#define Printv(v)                                                              \
    {                                                                          \
        FOREACH(x, v) { cout << x << " "; }                                    \
        cout << "\n";                                                          \
    }
template <typename T = string> inline void eputs(T s) {
    cout << s << "\n";
    exit(0);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    std::fill((T *)array, (T *)(array + N), val);
}
template <typename T> using PQG = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using PQ = priority_queue<T>;

typedef long long ll;
typedef unsigned long long ul;
typedef vector<ll> VL;
typedef pair<ll, ll> PL;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const double PI = atan(1.0) * 4.0;
// const int MOD = 998244353;
const ll LINF = 1e18;
const ll dx[] = {1, 0, -1, 0};
const ll dy[] = {0, 1, 0, -1};

void cinfast() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}
class MinimumCostFlow {
    struct Edge {
        const unsigned int to;  // 行き先のノードid
        long long flow;         // 流量
        const long long cap;    // 容量
        const long long cost;   // コスト
        const unsigned int rev; // 逆辺のノードid
        const bool is_rev;      // 逆辺かどうか
        Edge(unsigned int to, long long flow, long long cap, long long cost,
             unsigned int rev, bool is_rev)
            : to(to), flow(flow), cost(cost), cap(cap), rev(rev),
              is_rev(is_rev) {
            assert(this->cap >= 0);
        }
    };

    const int num_node;                   // 頂点数
    std::vector<std::vector<Edge>> graph; // グラフの隣接リスト表現
    bool have_negative_cost = false;      // 負辺があるか

  public:
    MinimumCostFlow(int num_node) : num_node(num_node) {
        graph.resize(num_node);
    }

    // fromからtoへ向かう容量cap、コストcostの辺をグラフに追加する
    void add_edge(unsigned int from, unsigned int to, long long cap,
                  long long cost) {
        graph.at(from).emplace_back(
            Edge(to, 0, cap, cost, graph.at(to).size(), false));
        graph.at(to).emplace_back(
            Edge(from, cap, cap, -cost, graph.at(from).size() - 1, true));
        have_negative_cost |= cost < 0;
    }

    // sからtへの流量fの最小費用流を求める
    // 流せない場合は-1を返す
    bool run(const unsigned int source, const unsigned int sink,
             long long flow) {

        // 負閉路がある場合、先に負閉路にそって流しておく
        // 負辺があっても負閉路ない場合はこの処理をskipしていい
        if(have_negative_cost) {
            remove_negative_cycles(source);
        }

        std::vector<int> prev_v(num_node, -1),
            prev_e(num_node, -1); // 直前の頂点と辺のidx
        std::vector<long long> potential(num_node, 0); // ポテンシャル

        // 負の辺がある場合、ポテンシャルをベルマンフォードで求めておく
        // 負の辺がない場合はこの処理をskipしていい
        if(have_negative_cost) {
            potential.assign(num_node, INT_MAX);
            potential.at(source) = 0;
            while(true) {
                bool updated = false;
                for(int v = 0; v < num_node; ++v) {
                    for(auto &e : graph.at(v)) {
                        if(e.cap - e.flow > 0) {
                            if(potential.at(v) == INT_MAX) {
                                continue;
                            }
                            if(potential.at(e.to) > potential.at(v) + e.cost) {
                                potential.at(e.to) = potential.at(v) + e.cost;
                                updated = true;
                            }
                        }
                    }
                }
                if(not updated) {
                    break;
                }
            }
        }

        while(flow > 0) {
            // ダイクストラ法を用いてポテンシャルを更新する
            std::priority_queue<std::pair<int, int>,
                                std::vector<std::pair<int, int>>,
                                std::greater<std::pair<int, int>>>
                que;
            std::vector<long long> distance(num_node,
                                            LINF); // 最短距離

            distance.at(source) = 0;
            que.push(std::make_pair(0, source));
            while(not que.empty()) {
                std::pair<int, int> p =
                    que.top(); // firstは最短距離、secondは頂点の番号
                que.pop();
                int v = p.second;
                if(distance.at(v) < p.first) {
                    continue;
                }
                for(int i = 0; i < graph.at(v).size(); ++i) {
                    Edge &e = graph.at(v).at(i);
                    if(e.cap - e.flow > 0 and
                       distance.at(e.to) > distance.at(v) + e.cost +
                                               potential.at(v) -
                                               potential.at(e.to)) {
                        distance.at(e.to) = distance.at(v) + e.cost +
                                            potential.at(v) -
                                            potential.at(e.to);
                        prev_v.at(e.to) = v;
                        prev_e.at(e.to) = i;
                        que.push(std::make_pair(distance.at(e.to), e.to));
                    }
                }
            }

            // これ以上流せない
            if(distance[sink] == LINF) {
                return false;
            }
            for(int v = 0; v < num_node; ++v) {
                potential.at(v) += distance.at(v);
            }

            // source-sink間で流せる量を求める
            long long d = flow;
            for(int v = sink; v != source; v = prev_v.at(v)) {
                auto &e = graph.at(prev_v.at(v)).at(prev_e.at(v));
                d = std::min(d, e.cap - e.flow);
            }

            flow -= d;
            for(int v = sink; v != source; v = prev_v.at(v)) {
                Edge &e = graph.at(prev_v.at(v)).at(prev_e.at(v));
                e.flow += d;
                graph.at(v).at(e.rev).flow -= d;
            }
        }
        return true;
    }

    // 最小費用を取得する
    int min_cost_flow() {
        int cost = 0;
        for(int u = 0; u < graph.size(); ++u) {
            for(int i = 0; i < graph.at(u).size(); ++i) {
                Edge &e = graph.at(u).at(i);
                if(not e.is_rev) {
                    cost += e.flow * e.cost;
                }
            }
        }
        return cost;
    }

  private:
    // 負閉路を除去する
    void remove_negative_cycles(const unsigned int source) {
        while(true) {
            // bellman-fordでsourceからの最短路を求める
            std::vector<int> prev_v(num_node, -1),
                prev_e(num_node, -1); // 直前の頂点と辺のidx
            std::vector<long long> distance(num_node, LINF);
            distance.at(source) = 0;

            int negative_cycle_idx = -1;
            for(int num = 0; num < num_node; ++num) {
                for(int u = 0; u < graph.size(); ++u) {
                    for(int i = 0; i < graph.at(u).size(); ++i) {
                        Edge &e = graph.at(u).at(i);

                        if(distance.at(u) == LINF) {
                            continue;
                        }

                        long long new_dist = distance.at(u) + e.cost;
                        if(e.cap - e.flow > 0 and
                           distance.at(e.to) > new_dist) {
                            distance.at(e.to) = new_dist;
                            prev_v.at(e.to) = u;
                            prev_e.at(e.to) = i;

                            if(num == num_node - 1) {
                                negative_cycle_idx = e.to;
                            }
                        }
                    }
                }
            }

            // 負閉路がない
            if(negative_cycle_idx == -1) {
                return;
            }

            long long d = LINF;
            std::vector<bool> used(num_node, false);
            int u = negative_cycle_idx;
            while(not used.at(u)) {
                used.at(u) = true;
                const Edge &e = graph.at(prev_v.at(u)).at(prev_e.at(u));
                d = std::min(d, e.cap - e.flow);
                u = prev_v.at(u);
            }

            assert(d != 0);

            std::fill(used.begin(), used.end(), false);
            // 閉路の開始点から見ていく
            while(not used.at(u)) {
                used.at(u) = true;
                Edge &e = graph.at(prev_v.at(u)).at(prev_e.at(u));
                e.flow += d;
                graph.at(e.to).at(e.rev).flow -= d;
                u = prev_v.at(u);
            }
        }
    }
};

using VVL = vector<VL>;

signed main() {
    LCIN(N, M);
    VVL G(N, VL(N, LINF));
    REP(i, N) G[i][i] = 0;
    MinimumCostFlow mcf(N + 2);
    ll s = N, t = s + 1;
    VL p(M), q(M), r(M);
    REP(i, M) {
        cin >> p[i] >> q[i] >> r[i];
        G[p[i]][q[i]] = -r[i];
    }
    REP(k, N) REP(i, N) REP(j, N) { G[i][j] = min(G[i][j], G[i][k] + G[k][j]); }
    ll Mlen = -G[0][N - 1];
    mcf.add_edge(s, 0, LINF, 0);
    mcf.add_edge(N - 1, t, LINF, Mlen);
    REP(i, M) {
        mcf.add_edge(p[i], q[i], LINF, -r[i]);
        mcf.add_edge(p[i], q[i], 1, -r[i] - INF);
    }
    mcf.run(s, t, 100000);
    cout << mcf.min_cost_flow() + M * INF << "\n";
}

### Prompt

Please create a solution in cpp to the following problem:

A video game company called ICPC (International Company for Playing and Competing) is now developing a new arcade game. The new game features a lot of branches. This makes the game enjoyable for everyone, since players can choose their routes in the game depending on their skills. Rookie players can choose an easy route to enjoy the game, and talented players can choose their favorite routes to get high scores.

In the game, there are many checkpoints connected by paths. Each path consists of several stages, and completing stages on a path leads players to the next checkpoint. The game ends when players reach a particular checkpoint. At some checkpoints, players can choose which way to go, so routes diverge at that time. Sometimes different routes join together at a checkpoint. The paths between checkpoints are directed, and there is no loop (otherwise, players can play the game forever). In other words, the structure of the game can be viewed as a DAG (directed acyclic graph), when considering paths between checkpoints as directed edges.

Recently, the development team completed the beta version of the game and received feedbacks from other teams. They were quite positive overall, but there are some comments that should be taken into consideration. Some testers pointed out that some routes were very short compared to the longest ones. Indeed, in the beta version, the number of stages in one play can vary drastically depending on the routes. Game designers complained many brilliant ideas of theirs were unused in the beta version because of the tight development schedule. They wanted to have more stages included in the final product.

However, it’s not easy to add more stages. this is an arcade game – if the playing time was too long, it would bring down the income of the game and owners of arcades would complain. So, the longest route of the final product can’t be longer than that of the beta version. Moreover, the producer of the game didn’t want to change the structure of paths (i.e., how the checkpoints connect to each other), since it would require rewriting the scenario, recording voices, creating new cutscenes, etc.

Considering all together, the producer decided to add as many new stages as possible, while keeping the maximum possible number of stages in one play and the structure of paths unchanged. How many new stages can be added to the game?



Input

N M
x1 y1 s1
.
.
.
xM yM sM


The first line of the input contains two positive integers N and M (2 ≤ N ≤ 100, 1 ≤ M ≤ 1000). N indicates the number of checkpoints, including the opening and ending of the game. M indicates the number of paths between checkpoints.

The following M lines describe the structure of paths in the beta version of the game. The i-th line contains three integers xi , yi and si (0 ≤ xi < yi ≤ N - 1, 1 ≤ si ≤ 1000), which describe that there is a path from checkpoint xi to yi consists of si stages. As for indices of the checkpoints, note that 0 indicates the opening of the game and N - 1 indicates the ending of the game. You can assume that, for every checkpoint i, there exists a route from the opening to the ending which passes through checkpoint i. You can also assume that no two paths connect the same pair of checkpoints.

Output

Output a line containing the maximum number of new stages that can be added to the game under the following constraints:

* You can’t increase the maximum possible number of stages in one play (i.e., the length of the longest route to the ending).
* You can’t change the structure of paths (i.e., how the checkpoints connect to each other).
* You can’t delete any stage that already exists in the beta version.

Examples

Input

3 3
0 1 5
1 2 3
0 2 2


Output

6


Input

2 1
0 1 10


Output

0


Input

4 6
0 1 5
0 2 5
0 3 5
1 2 5
1 3 5
2 3 5


Output

20

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define bitcnt __builtin_popcount
#define SZ(x) ((ll)(x).size())
#define fi first
#define se second
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define DCIN(...)                                                              \
    double __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"
#define Printv(v)                                                              \
    {                                                                          \
        FOREACH(x, v) { cout << x << " "; }                                    \
        cout << "\n";                                                          \
    }
template <typename T = string> inline void eputs(T s) {
    cout << s << "\n";
    exit(0);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    std::fill((T *)array, (T *)(array + N), val);
}
template <typename T> using PQG = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using PQ = priority_queue<T>;

typedef long long ll;
typedef unsigned long long ul;
typedef vector<ll> VL;
typedef pair<ll, ll> PL;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const double PI = atan(1.0) * 4.0;
// const int MOD = 998244353;
const ll LINF = 1e18;
const ll dx[] = {1, 0, -1, 0};
const ll dy[] = {0, 1, 0, -1};

void cinfast() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}
class MinimumCostFlow {
    struct Edge {
        const unsigned int to;  // 行き先のノードid
        long long flow;         // 流量
        const long long cap;    // 容量
        const long long cost;   // コスト
        const unsigned int rev; // 逆辺のノードid
        const bool is_rev;      // 逆辺かどうか
        Edge(unsigned int to, long long flow, long long cap, long long cost,
             unsigned int rev, bool is_rev)
            : to(to), flow(flow), cost(cost), cap(cap), rev(rev),
              is_rev(is_rev) {
            assert(this->cap >= 0);
        }
    };

    const int num_node;                   // 頂点数
    std::vector<std::vector<Edge>> graph; // グラフの隣接リスト表現
    bool have_negative_cost = false;      // 負辺があるか

  public:
    MinimumCostFlow(int num_node) : num_node(num_node) {
        graph.resize(num_node);
    }

    // fromからtoへ向かう容量cap、コストcostの辺をグラフに追加する
    void add_edge(unsigned int from, unsigned int to, long long cap,
                  long long cost) {
        graph.at(from).emplace_back(
            Edge(to, 0, cap, cost, graph.at(to).size(), false));
        graph.at(to).emplace_back(
            Edge(from, cap, cap, -cost, graph.at(from).size() - 1, true));
        have_negative_cost |= cost < 0;
    }

    // sからtへの流量fの最小費用流を求める
    // 流せない場合は-1を返す
    bool run(const unsigned int source, const unsigned int sink,
             long long flow) {

        // 負閉路がある場合、先に負閉路にそって流しておく
        // 負辺があっても負閉路ない場合はこの処理をskipしていい
        if(have_negative_cost) {
            remove_negative_cycles(source);
        }

        std::vector<int> prev_v(num_node, -1),
            prev_e(num_node, -1); // 直前の頂点と辺のidx
        std::vector<long long> potential(num_node, 0); // ポテンシャル

        // 負の辺がある場合、ポテンシャルをベルマンフォードで求めておく
        // 負の辺がない場合はこの処理をskipしていい
        if(have_negative_cost) {
            potential.assign(num_node, INT_MAX);
            potential.at(source) = 0;
            while(true) {
                bool updated = false;
                for(int v = 0; v < num_node; ++v) {
                    for(auto &e : graph.at(v)) {
                        if(e.cap - e.flow > 0) {
                            if(potential.at(v) == INT_MAX) {
                                continue;
                            }
                            if(potential.at(e.to) > potential.at(v) + e.cost) {
                                potential.at(e.to) = potential.at(v) + e.cost;
                                updated = true;
                            }
                        }
                    }
                }
                if(not updated) {
                    break;
                }
            }
        }

        while(flow > 0) {
            // ダイクストラ法を用いてポテンシャルを更新する
            std::priority_queue<std::pair<int, int>,
                                std::vector<std::pair<int, int>>,
                                std::greater<std::pair<int, int>>>
                que;
            std::vector<long long> distance(num_node,
                                            LINF); // 最短距離

            distance.at(source) = 0;
            que.push(std::make_pair(0, source));
            while(not que.empty()) {
                std::pair<int, int> p =
                    que.top(); // firstは最短距離、secondは頂点の番号
                que.pop();
                int v = p.second;
                if(distance.at(v) < p.first) {
                    continue;
                }
                for(int i = 0; i < graph.at(v).size(); ++i) {
                    Edge &e = graph.at(v).at(i);
                    if(e.cap - e.flow > 0 and
                       distance.at(e.to) > distance.at(v) + e.cost +
                                               potential.at(v) -
                                               potential.at(e.to)) {
                        distance.at(e.to) = distance.at(v) + e.cost +
                                            potential.at(v) -
                                            potential.at(e.to);
                        prev_v.at(e.to) = v;
                        prev_e.at(e.to) = i;
                        que.push(std::make_pair(distance.at(e.to), e.to));
                    }
                }
            }

            // これ以上流せない
            if(distance[sink] == LINF) {
                return false;
            }
            for(int v = 0; v < num_node; ++v) {
                potential.at(v) += distance.at(v);
            }

            // source-sink間で流せる量を求める
            long long d = flow;
            for(int v = sink; v != source; v = prev_v.at(v)) {
                auto &e = graph.at(prev_v.at(v)).at(prev_e.at(v));
                d = std::min(d, e.cap - e.flow);
            }

            flow -= d;
            for(int v = sink; v != source; v = prev_v.at(v)) {
                Edge &e = graph.at(prev_v.at(v)).at(prev_e.at(v));
                e.flow += d;
                graph.at(v).at(e.rev).flow -= d;
            }
        }
        return true;
    }

    // 最小費用を取得する
    int min_cost_flow() {
        int cost = 0;
        for(int u = 0; u < graph.size(); ++u) {
            for(int i = 0; i < graph.at(u).size(); ++i) {
                Edge &e = graph.at(u).at(i);
                if(not e.is_rev) {
                    cost += e.flow * e.cost;
                }
            }
        }
        return cost;
    }

  private:
    // 負閉路を除去する
    void remove_negative_cycles(const unsigned int source) {
        while(true) {
            // bellman-fordでsourceからの最短路を求める
            std::vector<int> prev_v(num_node, -1),
                prev_e(num_node, -1); // 直前の頂点と辺のidx
            std::vector<long long> distance(num_node, LINF);
            distance.at(source) = 0;

            int negative_cycle_idx = -1;
            for(int num = 0; num < num_node; ++num) {
                for(int u = 0; u < graph.size(); ++u) {
                    for(int i = 0; i < graph.at(u).size(); ++i) {
                        Edge &e = graph.at(u).at(i);

                        if(distance.at(u) == LINF) {
                            continue;
                        }

                        long long new_dist = distance.at(u) + e.cost;
                        if(e.cap - e.flow > 0 and
                           distance.at(e.to) > new_dist) {
                            distance.at(e.to) = new_dist;
                            prev_v.at(e.to) = u;
                            prev_e.at(e.to) = i;

                            if(num == num_node - 1) {
                                negative_cycle_idx = e.to;
                            }
                        }
                    }
                }
            }

            // 負閉路がない
            if(negative_cycle_idx == -1) {
                return;
            }

            long long d = LINF;
            std::vector<bool> used(num_node, false);
            int u = negative_cycle_idx;
            while(not used.at(u)) {
                used.at(u) = true;
                const Edge &e = graph.at(prev_v.at(u)).at(prev_e.at(u));
                d = std::min(d, e.cap - e.flow);
                u = prev_v.at(u);
            }

            assert(d != 0);

            std::fill(used.begin(), used.end(), false);
            // 閉路の開始点から見ていく
            while(not used.at(u)) {
                used.at(u) = true;
                Edge &e = graph.at(prev_v.at(u)).at(prev_e.at(u));
                e.flow += d;
                graph.at(e.to).at(e.rev).flow -= d;
                u = prev_v.at(u);
            }
        }
    }
};

using VVL = vector<VL>;

signed main() {
    LCIN(N, M);
    VVL G(N, VL(N, LINF));
    REP(i, N) G[i][i] = 0;
    MinimumCostFlow mcf(N + 2);
    ll s = N, t = s + 1;
    VL p(M), q(M), r(M);
    REP(i, M) {
        cin >> p[i] >> q[i] >> r[i];
        G[p[i]][q[i]] = -r[i];
    }
    REP(k, N) REP(i, N) REP(j, N) { G[i][j] = min(G[i][j], G[i][k] + G[k][j]); }
    ll Mlen = -G[0][N - 1];
    mcf.add_edge(s, 0, LINF, 0);
    mcf.add_edge(N - 1, t, LINF, Mlen);
    REP(i, M) {
        mcf.add_edge(p[i], q[i], LINF, -r[i]);
        mcf.add_edge(p[i], q[i], 1, -r[i] - INF);
    }
    mcf.run(s, t, 100000);
    cout << mcf.min_cost_flow() + M * INF << "\n";
}

```