<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

298. King Berl VI
Time limit per test: 0.75 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



King Berl VI has N daughters and no sons. During his long life he gave a number of promises to his daughters. All the promises have the following wording: "daughter Xi, I promise to give you dowry not less than Ci burles more than to daughter Yi", where i represents the number of the promise. Before his death the king decided to give some amount of money to each daughter. As far as he was the fair king, he decided to fullfill all his promises. But he was not only fair but also very greedy, he decided that he can give negative amount of burles as a dowry (i.e. daughter should pay this amount of burles to the treasury). Because of his born greed and by advice of the minister of finances, he made a decision that absolute value of each dowry should not exceed 10000 burles and the difference between dowry of the oldest and of the youngest daughters should be as small as possible (note, this value can be negative).

I.e. if the dowry given to the i-th daughter is Ai, folllowing conditions should be satisfied:
-10000≤ Ai≤ 10000
AN - A1 should be minimal


Input
The fist line of the input file contains two integers numbers N and M (2≤ N≤ 10000; 0≤ M≤ 100000), where N is the number of daughters and M is the number of promises. The following M lines contain the description of promises in the following form: Xi, Yi, Ci (1≤ Xi, Yi≤ N; Xi≠ Yi; 0≤ Ci≤ 1000). The youngest daughter has the number one, the oldest — N. Each pair Xi, Yi can appear in the input several times.

Output
Write to the output number -1 if there is no solution for the problem (i.e. there is no sequence of N integers which satisfies all described above requirements). Write to the output N integer numbers — the amount of dowry of each daughter in burles, if solution exists. If there are several solutions output any of them.

Example(s)
sample input
sample output
4 5
2 1 1
3 1 2
3 2 3
4 2 1
4 3 2
-3 -2 1 3

sample input
sample output
2 2
1 2 0
2 1 0
-7 -7

<|response|>
## 1) Abridged problem statement (concise)

There are `N` daughters and `M` promises. Each promise `(X, Y, C)` means:

> `A[X] ≥ A[Y] + C`

We must output integer dowries `A[1..N]` such that:

- All promises are satisfied.
- `-10000 ≤ A[i] ≤ 10000` for every `i`.
- The quantity `A[N] − A[1]` (oldest minus youngest) is **as small as possible** (it may be negative).

If impossible, output `-1`. Otherwise output any optimal assignment.

Constraints: `N ≤ 10000`, `M ≤ 100000`.

---

## 2) Key observations

1. **Difference constraints graph**  
   Constraint `A[X] ≥ A[Y] + C` is a directed edge `Y → X` with weight `C`, meaning:  
   along edge `u→v(w)`, enforce `A[v] ≥ A[u] + w`.

2. **Cycles and feasibility via SCC**  
   In a directed cycle, summing inequalities yields:
   `A[start] ≥ A[start] + (sum of weights on cycle)`  
   So if a cycle has **positive total weight**, impossible.  
   With all weights nonnegative here (`C ≥ 0`), **any positive edge inside a strongly connected component (SCC)** makes the SCC impossible (because you can traverse edges to form a cycle including it).  
   Therefore:
   - If an edge `(u→v,w)` lies within the same SCC and `w > 0` ⇒ **no solution**.
   - Otherwise SCCs can be compressed into a **DAG**.

3. **Constructing values on the SCC-DAG**  
   After SCC compression, constraints become:
   `val[cv] ≥ val[cu] + w` on DAG edges `cu→cv(w)`.  
   A standard way to build one feasible solution:
   - Initialize all component values to the minimum allowed `-10000`.
   - Topologically process DAG and relax: `val[v] = max(val[v], val[u] + w)`.

   This guarantees constraints but may leave “slack”. A second “tightening” pass is useful:
   - From constraint `val[v] ≥ val[u] + w` we also have `val[u] ≤ val[v] − w`.
   - In reverse topological order, set  
     `val[u] = min_{u→v(w)} (val[v] − w)` when `u` has outgoing edges.  
   This raises earlier components as much as possible while staying feasible, often improving the objective later.

4. **Optimization: minimize `A[N] − A[1]`**  
   Let `K = A[1] − A[N]`. Minimizing `A[N] − A[1]` is equivalent to **maximizing** `K`.  
   Add an extra constraint:
   `A[1] ≥ A[N] + K`  (edge `N → 1` with weight `K`).

   If we can check feasibility for a given `K`, then feasibility is monotone in `K`:
   - Larger `K` makes constraints harder.
   - So we can **binary search** the maximum feasible `K`.

   Since each `A[i] ∈ [-10000,10000]`, we have `K = A[1]-A[N] ∈ [-20000,20000]`.

---

## 3) Full solution approach

### Step A: Build feasibility checker `check(extra_edge)`
Input: original promises + optionally one extra constraint `(1, N, K)` (in original `(X,Y,C)` form).

1. Build directed graph edges `Y → X` (unweighted for SCC).
2. Compute SCCs (Kosaraju or Tarjan).
3. If any original edge lies within an SCC with `C > 0` ⇒ impossible.
   - Also if the extra edge ends up within one SCC, treat it as impossible for this check (it forces a constraint inside a cycle and breaks monotonic handling cleanly).
4. Compress SCCs into component DAG with weighted edges.
5. Compute component values:
   - Forward topo relaxation from `-10000`.
   - Reverse topo tightening to remove slack.
6. Expand to vertex values `A[i]=val[SCC[i]]` and ensure all in `[-10000,10000]`.

Return `(feasible, assignment)`.

### Step B: Find optimal answer
1. Run `check(no extra edge)`:
   - If infeasible ⇒ print `-1`.
2. Binary search `K ∈ [-20000,20000]`:
   - Test feasibility with extra constraint `A[1] ≥ A[N] + K`.
   - Keep the best feasible assignment; push `K` higher if feasible.
3. Output the assignment for the maximum feasible `K`.  
   If none feasible with extra edge (rare edge-case), output the base assignment.

Complexity:
- Each `check`: `O(N + M)` (SCC + DAG passes).
- Binary search over ~40001 values: `O((N+M) log 40000)` ≈ `O((N+M) * 16)`.

---

## 4) C++ implementation (detailed comments)

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

/*
  We solve system of constraints:
    A[x] >= A[y] + c
  with bounds -10000 <= A[i] <= 10000,
  and minimize A[N] - A[1].

  Approach:
    - Convert each constraint to directed edge y -> x with weight c.
    - SCC compression: any positive-weight edge inside SCC => impossible.
    - On compressed DAG, compute feasible values in [-10000,10000]:
        forward topo relaxation from -10000,
        then reverse topo "tightening".
    - Optimize objective by binary searching K = A[1] - A[N],
      i.e. add constraint A[1] >= A[N] + K.
*/

struct SCCKosaraju {
    int n;
    vector<vector<int>> g, rg;
    vector<int> comp, order;
    vector<char> vis;

    SCCKosaraju(int n=0) { init(n); }

    void init(int n_) {
        n = n_;
        g.assign(n, {});
        rg.assign(n, {});
    }

    void add_edge(int u, int v) {
        g[u].push_back(v);
        rg[v].push_back(u);
    }

    void dfs1(int u) {
        vis[u] = 1;
        for (int v : g[u]) if (!vis[v]) dfs1(v);
        order.push_back(u);
    }

    void dfs2(int u, int cid) {
        comp[u] = cid;
        for (int v : rg[u]) if (comp[v] == -1) dfs2(v, cid);
    }

    int build() {
        vis.assign(n, 0);
        order.clear();
        for (int i = 0; i < n; i++) if (!vis[i]) dfs1(i);
        reverse(order.begin(), order.end());

        comp.assign(n, -1);
        int cid = 0;
        for (int u : order) {
            if (comp[u] == -1) {
                dfs2(u, cid);
                cid++;
            }
        }
        return cid; // number of components
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<tuple<int,int,int>> edges;
    edges.reserve(M);
    for (int i = 0; i < M; i++) {
        int X, Y, C;
        cin >> X >> Y >> C;
        --X; --Y;
        edges.emplace_back(X, Y, C);
    }

    auto check = [&](const vector<tuple<int,int,int>>& extra_edges)
        -> pair<bool, vector<int>>
    {
        // 1) Build SCC structure on graph with edges (Y -> X)
        SCCKosaraju scc(N);
        for (auto [x,y,c] : edges) scc.add_edge(y, x);
        for (auto [x,y,c] : extra_edges) scc.add_edge(y, x);

        int K = scc.build(); // number of SCCs

        // 2) Feasibility inside SCC: any positive weight inside SCC => impossible
        for (auto [x,y,c] : edges) {
            if (scc.comp[x] == scc.comp[y] && c > 0) {
                return {false, {}};
            }
        }
        // For extra edge, we reject if it falls inside SCC (keeps binary search clean)
        for (auto [x,y,c] : extra_edges) {
            if (scc.comp[x] == scc.comp[y]) {
                return {false, {}};
            }
        }

        // 3) Build compressed DAG with weights: comp(y) -> comp(x) with weight c
        vector<vector<pair<int,int>>> dag(K);
        vector<int> indeg(K, 0);

        auto add_comp_edge = [&](int cu, int cv, int w) {
            dag[cu].push_back({cv, w});
            indeg[cv]++;
        };

        for (auto [x,y,c] : edges) {
            int cx = scc.comp[x], cy = scc.comp[y];
            if (cx != cy) add_comp_edge(cy, cx, c);
        }
        for (auto [x,y,c] : extra_edges) {
            int cx = scc.comp[x], cy = scc.comp[y];
            if (cx != cy) add_comp_edge(cy, cx, c);
        }

        // 4) Forward topo pass: minimal feasible values starting at -10000
        vector<int> val(K, -10000);
        queue<int> q;
        for (int i = 0; i < K; i++) if (indeg[i] == 0) q.push(i);

        vector<int> topo;
        topo.reserve(K);

        while (!q.empty()) {
            int u = q.front(); q.pop();
            topo.push_back(u);
            for (auto [v,w] : dag[u]) {
                val[v] = max(val[v], val[u] + w);
                indeg[v]--;
                if (indeg[v] == 0) q.push(v);
            }
        }

        // 5) Reverse topo tightening: raise val[u] as much as possible while keeping constraints
        // If u has outgoing edges, then val[u] <= min(val[v] - w)
        for (int i = (int)topo.size() - 1; i >= 0; i--) {
            int u = topo[i];
            int best = 10001; // sentinel meaning "no outgoing edges"
            for (auto [v,w] : dag[u]) best = min(best, val[v] - w);
            if (best < 10001) val[u] = best;
        }

        // 6) Expand back to vertices and check bounds
        vector<int> A(N);
        for (int i = 0; i < N; i++) {
            A[i] = val[scc.comp[i]];
            if (A[i] < -10000 || A[i] > 10000) return {false, {}};
        }
        return {true, A};
    };

    // Base feasibility
    auto [base_ok, base_A] = check({});
    if (!base_ok) {
        cout << -1 << "\n";
        return 0;
    }

    // Binary search K = A[1] - A[N] in [-20000, 20000]
    int lo = -20000, hi = 20000;
    vector<int> best;

    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        // Add constraint: A[0] >= A[N-1] + mid
        auto [ok, A] = check({{0, N-1, mid}});
        if (ok) {
            best = std::move(A);
            lo = mid + 1; // try bigger K
        } else {
            hi = mid - 1;
        }
    }

    if (best.empty()) best = base_A;

    for (int i = 0; i < N; i++) {
        if (i) cout << ' ';
        cout << best[i];
    }
    cout << "\n";
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
from collections import deque

# Constraints:
#   A[x] >= A[y] + c
# Convert to edge y -> x with weight c.
# Use SCC (Kosaraju), compress to DAG, do topo DP + tighten,
# then binary search K where A[0] >= A[n-1] + K.

sys.setrecursionlimit(1_000_000)

def kosaraju_scc(n, adj, radj):
    """Return (comp, k) where comp[u] is SCC id in [0..k-1]."""
    vis = [False] * n
    order = []

    def dfs1(u):
        vis[u] = True
        for v in adj[u]:
            if not vis[v]:
                dfs1(v)
        order.append(u)

    for i in range(n):
        if not vis[i]:
            dfs1(i)

    comp = [-1] * n
    k = 0

    def dfs2(u, cid):
        comp[u] = cid
        for v in radj[u]:
            if comp[v] == -1:
                dfs2(v, cid)

    for u in reversed(order):
        if comp[u] == -1:
            dfs2(u, k)
            k += 1

    return comp, k


def check(n, edges, extra_edges):
    """
    edges: list of (x, y, c) meaning A[x] >= A[y] + c
    extra_edges: same format, additional constraints (used for binary search)
    returns (ok, A)
    """

    # Build graph for SCC using only directions (y -> x)
    adj = [[] for _ in range(n)]
    radj = [[] for _ in range(n)]

    def add_dir(u, v):
        adj[u].append(v)
        radj[v].append(u)

    for x, y, c in edges:
        add_dir(y, x)
    for x, y, c in extra_edges:
        add_dir(y, x)

    comp, k = kosaraju_scc(n, adj, radj)

    # Positive weight within SCC => impossible
    for x, y, c in edges:
        if comp[x] == comp[y] and c > 0:
            return False, []

    # Reject extra edge if it lands inside an SCC (keeps binary search monotone & simple)
    for x, y, c in extra_edges:
        if comp[x] == comp[y]:
            return False, []

    # Build compressed DAG with weights: comp(y) -> comp(x) with weight c
    dag = [[] for _ in range(k)]
    indeg = [0] * k

    def add_comp_edge(cu, cv, w):
        dag[cu].append((cv, w))
        indeg[cv] += 1

    for x, y, c in edges:
        cx, cy = comp[x], comp[y]
        if cx != cy:
            add_comp_edge(cy, cx, c)

    for x, y, c in extra_edges:
        cx, cy = comp[x], comp[y]
        if cx != cy:
            add_comp_edge(cy, cx, c)

    # Forward topo DP: start at -10000
    val = [-10000] * k
    q = deque([i for i in range(k) if indeg[i] == 0])
    topo = []

    indeg_work = indeg[:]  # Kahn's algorithm modifies indegree
    while q:
        u = q.popleft()
        topo.append(u)
        for v, w in dag[u]:
            nv = val[u] + w
            if nv > val[v]:
                val[v] = nv
            indeg_work[v] -= 1
            if indeg_work[v] == 0:
                q.append(v)

    # Reverse topo tightening:
    # val[u] <= min(val[v] - w) over outgoing edges u->v(w)
    for u in reversed(topo):
        best = None
        for v, w in dag[u]:
            cand = val[v] - w
            if best is None or cand < best:
                best = cand
        if best is not None:
            val[u] = best

    # Expand to original vertices and check bounds
    A = [0] * n
    for i in range(n):
        A[i] = val[comp[i]]
        if A[i] < -10000 or A[i] > 10000:
            return False, []

    return True, A


def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))

    edges = []
    for _ in range(m):
        x = int(next(it)) - 1
        y = int(next(it)) - 1
        c = int(next(it))
        edges.append((x, y, c))

    # Base feasibility
    ok, base = check(n, edges, [])
    if not ok:
        sys.stdout.write("-1\n")
        return

    # Binary search K in [-20000, 20000] for constraint A[0] >= A[n-1] + K
    lo, hi = -20000, 20000
    best = None

    while lo <= hi:
        mid = (lo + hi) // 2
        ok, A = check(n, edges, [(0, n - 1, mid)])
        if ok:
            best = A
            lo = mid + 1
        else:
            hi = mid - 1

    if best is None:
        best = base

    sys.stdout.write(" ".join(map(str, best)) + "\n")


if __name__ == "__main__":
    solve()
```

---

If you want, I can also provide:
- a proof sketch of why “positive edge inside SCC ⇒ impossible”, and/or
- an alternative Bellman–Ford/SPFA-based solution (simpler conceptually, but typically slower here).