## 1) Abridged problem statement

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

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

The system evolves by repeatedly choosing any active vertex and **firing** it:
- each **incoming** arc to that vertex decreases by 1,
- each **outgoing** arc increases by 1.

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

Output for each vertex `1` if it is alive, else `0`.

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

---

## 2) Detailed editorial (explaining the solution)

### Key simplifications

#### A) Only whether a mark is zero matters
For “can a vertex become active”, what blocks activity is an incoming arc being **zero** (because activity requires all incoming marks > 0).  
If an arc is already positive, it can be thought of as “available”; exact magnitude doesn’t matter for the *existence* of deadlocks/aliveness classification used here. Thus the solution only distinguishes:
- `w == 0`  (blocking token missing)
- `w > 0`   (already has token)

#### B) Once a vertex is “not alive”, everything reachable from it is “not alive”
Intuition: if there exists a sequence of fires that can make `u` lose the property “alive”, then vertices downstream can be deprived of required tokens as well. The official solution uses a monotonicity argument: “not alive” propagates along edges, so we can mark all vertices reachable from a “bad” vertex as also bad.

So: find a set of vertices that are definitely **not alive**, then DFS/BFS along **all edges** to mark everything reachable as not alive.

---

### What makes a vertex definitely not alive?

#### 1) A zero self-loop kills the vertex immediately
If there is an edge `u -> u` with initial mark `0`, then vertex `u` can never be active:
- To fire `u`, all incoming arcs must be positive; but the self-loop is incoming and remains stuck at 0 unless `u` fires.
- Catch-22: `u` can’t fire to increase it, because it’s needed to be positive to fire.

Therefore: `u` is **not alive**.

(If the self-loop has `w>0`, it doesn’t create a fundamental obstruction for the reasoning here, so it’s ignored.)

#### 2) Any directed cycle consisting only of zero-mark edges makes its vertices not alive
Consider only edges with `w==0`. If there is a directed cycle of length > 1 among these edges, no vertex on that cycle can ever get all its incoming arcs positive, because each vertex on the cycle has at least one incoming zero edge from another vertex in the same cycle. To increase those cycle edges, some vertex on the cycle must fire first, but none can become active due to the zero incoming requirement.

This is exactly captured by **strongly connected components (SCCs)** in the graph of `w==0` edges:
- If an SCC has size > 1, it contains a directed cycle ⇒ all its vertices are not alive.

So: build graph **H** containing only edges with `w==0` (except ignore `u->u` here and handle self-loops separately), compute SCCs. Any vertex in an SCC of size > 1 is not alive.

---

### Final propagation

Let initial bad set be:
- vertices with a zero self-loop, and
- vertices in SCCs (in the zero-edge graph) of size > 1.

Then perform DFS/BFS from every bad vertex over **the full graph G (all edges regardless of w)** and mark reachable vertices as bad too.

Remaining vertices are alive.

---

### Complexity
- Building graphs: `O(N + M)`
- SCC (Kosaraju): `O(N + M0)` where `M0` is number of zero edges (≤ M)
- DFS propagation: `O(N + M)`
Works comfortably within limits.

---

## 3) 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;
}
```

---

## 4) Python solution (same approach, with detailed comments)

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

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

    # all_edges: full graph G (all edges regardless of weight)
    all_edges = [[] for _ in range(n)]

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

    # remember zero self-loops separately
    has_zero_self_loop = [False] * n

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

        # store edge in full graph
        all_edges[u].append(v)

        if w == 0:
            if u == v:
                has_zero_self_loop[u] = True
            else:
                adj[u].append(v)
                radj[v].append(u)

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

    def dfs1(u: int) -> None:
        """First pass DFS to compute finishing order."""
        visited[u] = True
        for v in adj[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_count = 0

    def dfs2(u: int, cid: int) -> None:
        """Second pass DFS on reversed graph to assign component id."""
        comp[u] = cid
        for v in radj[u]:
            if comp[v] == -1:
                dfs2(v, cid)

    # process in reverse finishing order
    for u in reversed(order):
        if comp[u] == -1:
            dfs2(u, comp_count)
            comp_count += 1

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

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

    # initial "bad" vertices:
    # - zero self-loop
    # - belongs to SCC with size > 1 in zero-edge graph (zero cycle)
    for u in range(n):
        if has_zero_self_loop[u] or comp_size[comp[u]] > 1:
            alive[u] = 0

    # propagate "not alive" along the full graph
    def propagate(u: int) -> None:
        """If u is not alive, mark all reachable vertices as not alive."""
        for v in all_edges[u]:
            if alive[v] == 1:
                alive[v] = 0
                propagate(v)

    for u in range(n):
        if alive[u] == 0:
            propagate(u)

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

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

---

## 5) Compressed editorial

- Only the **zero vs positive** status of each arc matters.
- Build two graphs:
  - **G**: all edges.
  - **H**: only edges with initial mark `0` (ignore self-loops here).
- A vertex is immediately **not alive** if it has a **zero self-loop**.
- Any SCC in **H** of size > 1 is a **cycle of zero edges** ⇒ all its vertices are **not alive**.
- From every not-alive vertex, DFS/BFS over **G** to mark all reachable vertices as not alive.
- Output 1 for the rest.

Time: `O(N+M)` (Kosaraju SCC + DFS).