<|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.

219. Synchrograph
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



In the theory of processes a special case of Petri nets is often considered, called synchrographs. Synchrograph can be represented as directed graph, each arc of which is marked with some non-negative integer number. The vertex of synchrograph is called active if all arcs incoming into this vertex are marked with the positive number.

Synchrograph operates in cycles. Each cycle one active vertex is nondeterministically selected and fired. The vertex fires the following way: the number on each arc incoming into this vertex is decreased by one, and the number on each arc outgoing from this vertex is increased by one. After that the set of active vertices is refreshed due to the new marks of the arcs and the next cycle takes place.

The vertex of synchrograph is called potentially alive if there is the sequence of fires, such that after it the vertex itself fires. The vertex is called alive if after any valid sequence of fires it is potentially alive.

For each vertex of synchrograph detect whether it is alive.

Input

The first line of the input file contains N and M — the number of vertices and arcs of synchrograph respectively (1 ≤ N ≤ 1000, 1 ≤ M ≤ 50000). Next M lines contain arc descriptions --- the beginning of the arc, the end of the arc and the number that this arc is initially marked with. No mark exceeds 109.

Output

For each vertex print 1 if it is alive and 0 in the other case.

Sample test(s)

Input
6 8
1 2 1
4 3 0
2 4 0
4 3 1
1 6 0
6 3 1
3 2 0
4 5 1000000000

Output
1
0
0
0
0
1

Note
11.12.2003. Clarification done: "For each vertex of synchrograph detect whether it is potentially alive" changed to "For each vertex of synchrograph detect whether it is alive".
Author:	Andrew Stankevich
Resource:	Summer Trainings 2003, Maloyaroslavets
Date:	2003-06-26

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

You are given a directed graph with **N** vertices and **M** arcs. Each arc has an initial **non‑negative** integer mark.

A vertex is **active** if **all its incoming arcs** currently have **positive** marks.

A step (“cycle”) chooses any active vertex and **fires** it:
- every **incoming** arc mark decreases by 1
- every **outgoing** arc mark increases by 1

A vertex is:
- **potentially alive** if there exists some valid firing sequence after which this vertex fires at least once.
- **alive** if **after any valid firing sequence**, it is still potentially alive.

For each vertex, output `1` if it is **alive**, else `0`.

Constraints: `N ≤ 1000`, `M ≤ 50000`, marks up to `1e9`.

---

## 2) Key observations needed to solve the problem

### Observation A — “Zero vs positive” is what matters for being blocked
A vertex is blocked from being active if it has **at least one incoming arc with mark 0**.  
For the aliveness characterization used in this task, the exact positive value (5 vs 1e9) is not essential—what matters is whether an arc is **0** (missing a required token) or **>0**.

### Observation B — A zero self-loop makes the vertex impossible to fire
If there is an arc `u → u` with mark `0`, then `u` can never become active:
- that self-loop is incoming to `u` and stays 0 unless `u` fires,
- but `u` cannot fire because it requires that arc to be positive.

So `u` is **not alive**.

### Observation C — A directed cycle of zero-mark edges is a permanent deadlock region
Consider the subgraph consisting only of arcs with initial mark `0` (ignore self-loops for a moment).  
If it contains a directed cycle (length ≥ 2), then no vertex on that cycle can ever be the **first** to fire to “create” tokens on those zero edges, because each vertex has at least one incoming zero edge from the cycle.

In graph terms: any **SCC** (strongly connected component) in the `w = 0` subgraph with **size > 1** contains such a cycle, hence all its vertices are **not alive**.

### Observation D — “Not alive” propagates forward along all edges
If a vertex `u` is not alive, then every vertex reachable from `u` in the original graph is also not alive (intuitively: downstream vertices can be deprived of the ability to eventually fire after some sequences).

So once we find an initial set of “certainly not alive” vertices, we can mark all vertices reachable from them (using **all edges**) as not alive too.

---

## 3) Full solution approach based on the observations

1. **Read input** and build:
   - `G`: adjacency list of the **full graph** (all arcs, regardless of mark).
   - `H`: adjacency list of the **zero-edge graph** (only arcs with `w == 0` and `u != v`).
   - `zeroSelf[u]`: whether there exists a **zero self-loop** `u → u` with `w == 0`.

2. **Compute SCCs in `H`** (Kosaraju or Tarjan).
   - For every SCC with size > 1, mark all its vertices as **not alive**.
   - Additionally, any `u` with `zeroSelf[u] == true` is **not alive**.

3. **Propagate not-aliveness**:
   - Run DFS/BFS in the full graph `G` starting from all currently-not-alive vertices.
   - Mark every reachable vertex as **not alive**.

4. Output for each vertex:
   - `1` if not marked “not alive”
   - `0` otherwise

**Complexity:**  
- SCC on zero-edges: `O(N + M0)` where `M0 ≤ M`
- Propagation DFS/BFS on full graph: `O(N + M)`
- Total: `O(N + M)` time, memory `O(N + M)`.

---

## 4) C++ Solution

```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<vector<int>> all;
vector<int> alive;

StronglyConnectedComponents scc;
vector<bool> has_zero_self_loop;

void read() {
    cin >> n >> m;
    all.resize(n);
    scc.init(n);
    has_zero_self_loop.resize(n);
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        all[u].push_back(v);
        if(w == 0) {
            if(u == v) {
                has_zero_self_loop[u] = true;
            } else {
                scc.add_edge(u, v);
            }
        }
    }
}

void dfs(int u) {
    for(int v: all[u]) {
        if(alive[v] == 1) {
            alive[v] = 0;
            dfs(v);
        }
    }
}

void solve() {
    // The problem is fairly simple, we just need to make a few observations:
    //     1) If a node is not alive, all nodes reachable from it are also not
    //        alive. This is trivial to prove.
    //     2) We don't actually care about the concrete w values, only whether
    //        they are 1 or 0.
    //     3) We might have self loops. If there is a w=0 self loop, then it's
    //        certainly impossible. If it's a w=1 self loop, it can be ignored.
    //     4) Arguably the main observation - if we have a w=0 cycle of > 1
    //        nodes, then all nodes in it can't be alive. This is generalized to
    //        the nodes in a strongly connected component. This is easy to show
    //        as there is always at least one incoming edge that can't fire.
    //     5) All other nodes are alive. In particular, a good intuition is to
    //        think about nodes that have in_degree = 0. They effectively let us
    //        generate tokens for free, which we can later propagate through the
    //        structure. If there are no such nodes, then we have cycles that
    //        have all incoming edges "full", or there is w=0 cycle. We can make
    //        an inductive argument by considering the "highest" nodes /
    //        strongly connected component.
    //
    // Then the solution is fairly simple - we keep two graphs G with all edges,
    // and H with only the 0 edges. We create the strongly connected components
    // in H, and if some of them has size > 1, all nodes are marked as not
    // alive. Finally we propagate down from every non alive node over the edges
    // of G. The time complexity is O(N+M) if we use Tarjan or Kosaraju for the
    // SCC.

    alive.assign(n, 1);
    scc.find_components();

    vector<int> comp_size(scc.comp_ids.size());
    for(int i = 0; i < n; i++) {
        comp_size[scc.comp[i]]++;
    }
    for(int i = 0; i < n; i++) {
        if(has_zero_self_loop[i] || comp_size[scc.comp[i]] > 1) {
            alive[i] = 0;
        }
    }
    for(int i = 0; i < n; i++) {
        if(alive[i] == 0) {
            dfs(i);
        }
    }
    for(int i = 0; i < n; i++) {
        cout << alive[i] << "\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 with detailed comments

```python
import sys
sys.setrecursionlimit(1_000_000)

def solve() -> None:
    input = sys.stdin.readline
    n, m = map(int, input().split())

    # Full graph G: used for forward propagation of "not alive"
    full = [[] for _ in range(n)]

    # Zero-edge graph H for SCC: only edges with w == 0 and u != v
    g = [[] for _ in range(n)]
    rg = [[] for _ in range(n)]

    # Track zero self-loops: u->u with w==0
    zero_self = [False] * n

    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1

        full[u].append(v)

        if w == 0:
            if u == v:
                zero_self[u] = True
            else:
                g[u].append(v)
                rg[v].append(u)

    # --- Kosaraju SCC on H (zero-edge graph) ---
    visited = [False] * n
    order = []

    def dfs1(u: int) -> None:
        visited[u] = True
        for v in g[u]:
            if not visited[v]:
                dfs1(v)
        order.append(u)

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

    comp = [-1] * n
    comp_cnt = 0

    def dfs2(u: int, cid: int) -> None:
        comp[u] = cid
        for v in rg[u]:
            if comp[v] == -1:
                dfs2(v, cid)

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

    # Component sizes
    comp_size = [0] * comp_cnt
    for u in range(n):
        comp_size[comp[u]] += 1

    # alive[u] = 1 if alive, 0 if not alive
    alive = [1] * n

    # Initial "definitely not alive":
    # - zero self-loop
    # - belongs to an SCC of size > 1 in zero-edge graph => zero cycle
    for u in range(n):
        if zero_self[u] or comp_size[comp[u]] > 1:
            alive[u] = 0

    # Propagate not-aliveness over the FULL graph
    # Iterative DFS to avoid recursion depth issues on large graphs.
    stack = [u for u in range(n) if alive[u] == 0]
    seen = [False] * n
    for u in stack:
        seen[u] = True

    while stack:
        u = stack.pop()
        for v in full[u]:
            if not seen[v]:
                seen[v] = True
                alive[v] = 0
                stack.append(v)

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

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

These implementations follow the same core idea:
1) detect “zero deadlock cores” via SCCs on zero-mark edges (+ zero self-loops),  
2) propagate their effect forward on the full graph,  
3) remaining vertices are alive.