<|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>
// #include <coding_library/graph/scc.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

class StronglyConnectedComponents {
  private:
    vector<bool> visited;

    void dfs1(int u) {
        visited[u] = true;
        for(int v: adj[u]) {
            if(!visited[v]) {
                dfs1(v);
            }
        }

        top_sort.push_back(u);
    }

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

  public:
    int n;
    vector<vector<int>> adj, radj;
    vector<int> comp, comp_ids, top_sort;

    StronglyConnectedComponents() {}
    StronglyConnectedComponents(int _n) { init(_n); }

    void add_edge(int u, int v) {
        adj[u].push_back(v);
        radj[v].push_back(u);
    }

    void init(int _n) {
        n = _n;
        comp_ids.clear();
        top_sort.clear();
        adj.assign(n, {});
        radj.assign(n, {});
    }

    void find_components() {
        comp.assign(n, -1);
        visited.assign(n, false);

        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                dfs1(i);
            }
        }

        reverse(top_sort.begin(), top_sort.end());
        for(int u: top_sort) {
            if(comp[u] == -1) {
                comp[u] = (int)comp_ids.size();
                comp_ids.push_back(comp[u]);
                dfs2(u);
            }
        }
    }
};

int n, m;
vector<tuple<int, int, int>> edges;

void read() {
    cin >> n >> m;
    edges.resize(m);
    for(int i = 0; i < m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        x--;
        y--;
        edges[i] = {x, y, c};
    }
}

pair<bool, vector<int>> check(vector<tuple<int, int, int>> extra_edges) {
    StronglyConnectedComponents 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);
    }
    scc.find_components();

    for(auto& [x, y, c]: edges) {
        if(scc.comp[x] == scc.comp[y] && c > 0) {
            return {false, {}};
        }
    }
    for(auto& [x, y, c]: extra_edges) {
        if(scc.comp[x] == scc.comp[y]) {
            return {false, {}};
        }
    }

    int num_comps = (int)scc.comp_ids.size();
    vector<vector<pair<int, int>>> comp_adj(num_comps);
    vector<int> indegree(num_comps, 0);

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

    vector<int> comp_val(num_comps, -10000);
    vector<int> topo_order;
    queue<int> q;
    for(int i = 0; i < num_comps; i++) {
        if(indegree[i] == 0) {
            q.push(i);
        }
    }

    while(!q.empty()) {
        int u = q.front();
        q.pop();
        topo_order.push_back(u);
        for(auto [v, c]: comp_adj[u]) {
            comp_val[v] = max(comp_val[v], comp_val[u] + c);
            indegree[v]--;
            if(indegree[v] == 0) {
                q.push(v);
            }
        }
    }

    for(int i = num_comps - 1; i >= 0; i--) {
        int u = topo_order[i], val = 10001;
        for(auto [v, c]: comp_adj[u]) {
            val = min(val, comp_val[v] - c);
        }

        if(val < 10001) {
            comp_val[u] = val;
        }
    }

    vector<int> ans(n);
    for(int i = 0; i < n; i++) {
        ans[i] = comp_val[scc.comp[i]];
        if(ans[i] < -10000 || ans[i] > 10000) {
            return {false, {}};
        }
    }

    return {true, ans};
}

void solve() {
    // Let's start with verifying if a valid configuration is possible, rather
    // than trying to minimize the difference. We will have edges (u -> v, c),
    // representing a[u] >= a[v] + c. If we had a DAG, it would be fairly to
    // check if this is possible to do this with DP - the 0 in degree nodes
    // will be assigned with -10000, and we recursively / in topological order
    // try to set the lowest allowed value. When there is a cycle, we can notice
    // that all edges with endpoints in it should actually have c = 0.
    // Otherwise, it's impossible which is easy to show with contradiction if we
    // look at the inequalities in the cycle. Furthermore, all nodes u in these
    // 0-cycles should be assigned the same value a[u]. This means we can simply
    // compress the strongly connected components, run the DP, check that there
    // is no edge with c > 0 in a SCC, and finally check that all values are
    // within [-10000; 10000] after running the DP. This check runs in O(n + m).
    // Something we should be careful about and will come in the last paragraph
    // is that we should "tighten" the constraints over the DAG after we do the
    // initial setting.
    //
    // Now let's try to get the lowest difference of a[n] - a[1]. We have an
    // oracle that quickly verifies that there is a solution, so we should think
    // if we could potentially exploit this. The standard approach is to
    // consider if we could potentially binary search on the answer, and it
    // turns out this is the case. Particularly, we can add a constraint a[1] >=
    // a[n] + K and binary search for the largest K for which this is possible
    // (the answer is then -K). There is a duality argument we could use here
    // too, but it's not hard to get convinced this is equivalent. Note that the
    // K we binary search over could also be negative for the case a[1] <= a[n]
    // so the bounds should be -20000 to 20000.
    //
    // There is a special case when adding the edge n -> 1 creates a cycle. In
    // this case, we would need K to be negative, which is non trivial to
    // handle. Instead, we first check if a solution exists without any extra
    // edges. If not, we output -1. Otherwise, we binary search but return false
    // whenever a cycle is created. If the binary search finds no valid K, it
    // means the edge always creates a cycle, implying nodes 1 and n are already
    // in the same SCC. In this case, the initial check({}) already gives the
    // minimal difference solution since 1 and n must either have the same
    // value, or there is a direct dependence between the two and the DP always
    // tries to minimize the new value. We should be careful about the fact that
    // we start from -10000 though. Consider the case of N depending on some
    // vertex v with a large delta, and on 1 with a smaller delta. Then running
    // the DP the critical constraint would be the one between N and v, while 1
    // will be set to -10000 by the DP. In other words there will be slack in
    // the 1-N constraint. However, it makes more sense to just assign 1 a
    // higher value so that the constraint 1-N becomes tight. This can be done
    // by doing a second pass over the reverse topological order, and increasing
    // the values if we can.
    //
    // There is also a Bellman-Ford solution that is significantly simpler and
    // without binary search, but it runs slower (the one described here is
    // O((n+m) log MAX)).

    auto [base_ok, base_ans] = check({});
    if(!base_ok) {
        cout << -1 << '\n';
        return;
    }

    int low = -20000, high = 20000, mid;
    vector<int> ans;
    while(low <= high) {
        mid = (low + high) / 2;
        auto [ok, res] = check({{0, n - 1, mid}});
        if(ok) {
            ans = res;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    if(ans.empty()) {
        ans = base_ans;
    }
    cout << ans << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    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()
```
