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

301. Boring. Hot. Summer...
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



"Hello, dear Dima Malikov.

If you still do not know me,

My name is Ignat..."

From the letter of Ignat (the biggest fan) to Dima Malikov.

You are the head of the ROVD of the village Big Valenki. Recently you got a message informing that some stranger hijacked a tractor and currenly is making his way from point X to point Y. The roads in the village are bidirectional and connect the pairs of junctions. Village has N junctions and M roads. Each road has some fixed length. Points X and Y are junctions. The hijacker certainly chose one of the shortest routes from X to Y. Your first deputy chief suggested that the criminal should be intercepted on the junction number 1, but you noticed that at the moment when the criminal could reach this junction he can actually be at one of A1 different points of the village (some of these points could be at the roads). Your second deputy chief suggested that interception should be arranged at the second junction. But you noticed again that at that time criminal could be at A2 different points of the village. The last suggestion came from N-th deputy chief, and you answered him with number AN. If the way of the criminal does not pass through the junction K for sure, AK will be equal to zero.

As you later noticed, the process of finding of A1, A2,..., AN sequence can be automated. You are to write a program which will find this sequence.

Input
The first line of the input contains three natural numbers N, X, Y (1≤ N≤ 2000; 1≤ X, Y≤ N). The second line contains the only number M (0≤ M≤ 200000). The following lines contains the description of roads. Each description is three integer numbers xi, yi, li — the pair of junctions it connects and its length. The lengths of all roads are integer numbers from 1 to 10000. Between each pair of junctions there is no more than one road. The road cannot connect junction to itself.

Output
Output the desired sequence.

Example(s)
sample input
sample output
6 2 5
9
1 2 1 1 3 10
1 6 1 4 6 1
6 5 1 2 6 2
3 6 1 5 3 1
4 5 1
2 1 0 0 1 1

sample input
sample output
4 1 4
5
1 2 1 1 4 2
1 3 1 2 4 1
3 4 1
1 3 3 1

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

You are given an undirected weighted graph with `N` junctions and `M` roads. A criminal starts at junction `X` and will travel to junction `Y` using **some shortest path** (if multiple shortest paths exist, any could be chosen).

For each junction `K = 1..N`, consider the time moment `t = dist(X, K)` (shortest distance from `X` to `K`). At that same time `t`, depending on which shortest `X→Y` path the criminal chose, he may be at multiple possible **points** in the village (junctions or interior points on roads).

Define `A_K` = number of distinct points where the criminal **could be** at time `dist(X,K)`, assuming he travels along a shortest route from `X` to `Y`. If junction `K` is not on any shortest `X→Y` route, then `A_K = 0`.

Output `A_1 ... A_N`.

---

## 2) Key observations needed to solve the problem

1. **Shortest paths are characterized by distances from `X`.**
   Run Dijkstra from `X`, obtaining `dist[u]`.

2. **Shortest-path edges form a DAG when oriented by increasing `dist`.**
   For an undirected edge `(u,v,w)`:
   - if `dist[u] + w == dist[v]`, we can direct it `u → v` in the shortest-path DAG.

3. **We only care about shortest paths that can still reach `Y`.**
   Some DAG nodes may be reachable from `X` but not lead to `Y`.
   If a node `u` cannot reach `Y` in the DAG, then no shortest `X→Y` path uses `u`.

4. **At time `t` (integer), criminal can be:**
   - **At a reachable vertex `u`** if `t == dist[u]` → contributes **1** possible point.
   - **Inside a directed shortest edge `u→v`** of length `w` at time `t` iff
     `dist[u] < t < dist[v]`. Since queries are at integer times `t = dist[K]`, interior points on edge contribute for integer times:
     \[
       t \in [dist[u]+1,\; dist[v]-1]
     \]
     Also the edge is usable only if after reaching `v`, a shortest continuation to `Y` exists ⇒ `reachable[v] == true`.

5. This becomes an offline counting problem:
   For each integer time `t`, count how many "active" contributions cover it:
   - vertex points: add `+1` at exactly `t = dist[u]`
   - edge interiors: add `+1` for all `t` in a range `[L,R]`

   We need answers only at times `t = dist[K]`. This is "range add + point query", solvable by a sweep line over events.

---

## 3) Full solution approach

### Step A: Dijkstra from `X`
Compute `dist[u] = shortest distance X→u` for all nodes.

Complexity: `O((N+M) log N)`.

---

### Step B: Build reverse adjacency of the shortest-path DAG
For each undirected edge `(u,v,w)`:
- if `dist[u] + w == dist[v]`, then DAG has `u → v`, so in the **reverse DAG** store `u` as a predecessor of `v`.

Let `dag_rev[v]` contain all predecessors `u` such that `u → v` is a shortest edge.

---

### Step C: Mark nodes that lie on some shortest `X→Y` path
Run DFS/BFS from `Y` on `dag_rev`:
- `reachable[u] = true` if `u` can reach `Y` following shortest edges (forward), i.e., if `Y` can reach `u` in the reverse graph.

If `reachable[K]` is false, then `A_K = 0`.

---

### Step D: Convert all contributions into sweep-line events

We will sweep over "time" values. Create events of form `(pos, type, data)` where:

- `type = 0` : IN event (adds +1 to active count)
- `type = 1` : QUERY event (record current active count)
- `type = 2` : OUT event (removes -1 from active count)

Important ordering at same `pos`: **IN before QUERY before OUT**, so sorting by `(pos, type)` works with type order `0,1,2`.

**1) Vertex contributions**
For each `u` with `reachable[u]`:
- add a point contribution at `t = dist[u]`.
Implement as:
- IN at `dist[u]`
- OUT at `dist[u]`
so it is active exactly at that coordinate during the query.

**2) Edge interior contributions**
For each directed shortest edge `u→v` (i.e., `dist[u]+w==dist[v]`) where `reachable[v]`:
- interior integer times are in `[dist[u]+1, dist[v]-1]`.
If `L <= R`, add:
- IN at `L`
- OUT at `R`

**3) Queries**
For each node `K` with `reachable[K]`:
- add QUERY at time `dist[K]` storing into `answer[K]`.

Sweep through sorted events maintaining `balance` (active count). At QUERY, set `answer[K] = balance`.

---

### Correctness intuition
At time `t = dist[K]`:
- Every reachable vertex with `dist==t` contributes 1 (being at that junction).
- Every usable shortest edge whose interior covers `t` contributes 1 (being somewhere inside that road at that moment).
The sweep-line count `balance` is exactly the number of these contributions, hence equals `A_K`.

---

### Complexity
- Dijkstra: `O((N+M) log N)`
- Building DAG reverse: `O(M)`
- DFS/BFS: `O(N+M)`
- Events: `O(N + M)`
- Sorting events: `O((N+M) log (N+M))`

Works within constraints (noting tight time limit; use fast I/O).

---

## 4) C++ implementation with detailed comments

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

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;
};

const int64_t inf = (int64_t)1e18 + 42;

int n, x, y, m;
vector<vector<pair<int, int>>> adj;

void read() {
    cin >> n >> x >> y;
    x--;
    y--;
    cin >> m;
    adj.assign(n, {});
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
}

void solve() {
    // We are only interested in shortest paths, so the first step is to build
    // the Dijkstra DAG of optimal edges. The Dijkstra will start from X, but we
    // also want to afterwards compute reachable(u) which will be true if Y is
    // reachable from u through the DAG (this can be done with one DFS).
    //
    // We are now interested in the number of points in the DAG that have
    // distance equal to dist(i) for each i. And we want to compute this for all
    // i quickly. Let's denote this with a function f(a) which will denote the
    // number of points with distance equal to a. We will maintain this in a
    // smart way, so then then we simply want to evaluate the function in N
    // points. We can first separately figure the contribution from points that
    // fall within a vertex - if u is a vertex with reachable(u) = true, then
    // f(dist(u)) should be increased by 1. Now we are left with the case of the
    // contribution coming from points on edges. Let's say we have an edge (u,
    // v), and reachable(v) = true. Then we can be on that edge at any point a,
    // such that dist(u) < a < dist(v). This is essentially a range of values.
    // We only care about integer query points, and we want to be careful about
    // not over-counting points that fall in vertices. Hence, we can increase
    // f(dist(u)+1), ..., f(dist(v)-1) by one, or one range per edge.
    //
    // This now ends up being a standard problem - we have N ranges, and N
    // queries, where for every query we want to figure out by how many ranges
    // it's covered. This can be done with splitting the ranges into a pair of
    // events - an IN event with "balance += 1" at L, and an OUT event with
    // "balance -= 1" at R. And we also add QUERY events that will look at the
    // balance. Priority should be IN, QUERY, OUT. Note that this approach is
    // offline, while online we could do segment trees but this is less pleasant
    // here as the edges have higher weights so we need to use a dynamic segment
    // tree / treap.
    //
    // All steps of the solution are in O((N + M) log M).

    vector<int64_t> dist(n, inf);
    priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<>>
        pq;
    dist[x] = 0;
    pq.push({0, x});
    while(!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if(d > dist[u]) {
            continue;
        }
        for(auto [v, w]: adj[u]) {
            if(dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    vector<vector<int>> dag_rev(n);
    for(int u = 0; u < n; u++) {
        for(auto [v, w]: adj[u]) {
            if(dist[u] + w == dist[v]) {
                dag_rev[v].push_back(u);
            }
        }
    }

    vector<bool> reachable(n, false);
    function<void(int)> dfs = [&](int u) {
        if(reachable[u]) {
            return;
        }
        reachable[u] = true;
        for(int v: dag_rev[u]) {
            dfs(v);
        }
    };
    dfs(y);

    vector<tuple<int64_t, int, int>> events;
    for(int u = 0; u < n; u++) {
        if(reachable[u]) {
            events.push_back({dist[u], 0, 0});
            events.push_back({dist[u], 2, 0});
        }
        for(auto [v, w]: adj[u]) {
            if(dist[u] + w == dist[v] && reachable[v]) {
                int64_t l = dist[u] + 1;
                int64_t r = dist[v] - 1;
                if(l <= r) {
                    events.push_back({l, 0, 0});
                    events.push_back({r, 2, 0});
                }
            }
        }
    }
    for(int k = 0; k < n; k++) {
        if(reachable[k]) {
            events.push_back({dist[k], 1, k});
        }
    }

    sort(events.begin(), events.end());

    vector<int> answer(n, 0);
    int balance = 0;
    for(auto [pos, type, data]: events) {
        if(type == 0) {
            balance++;
        } else if(type == 1) {
            answer[data] = balance;
        } else {
            balance--;
        }
    }

    cout << answer << '\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
import heapq

INF = 10**30

def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    X = next(it) - 1
    Y = next(it) - 1
    M = next(it)

    # Undirected weighted graph
    adj = [[] for _ in range(N)]
    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        w = next(it)
        adj[u].append((v, w))
        adj[v].append((u, w))

    # ---- Step A: Dijkstra from X ----
    dist = [INF] * N
    dist[X] = 0
    pq = [(0, X)]  # (distance, node)

    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))

    # ---- Step B: Reverse shortest-path DAG ----
    # If dist[u] + w == dist[v], then u -> v is a shortest-path DAG edge.
    dag_rev = [[] for _ in range(N)]
    for u in range(N):
        du = dist[u]
        if du >= INF:
            continue
        for v, w in adj[u]:
            if du + w == dist[v]:
                dag_rev[v].append(u)

    # ---- Step C: Mark nodes that can reach Y (reverse DFS/BFS from Y) ----
    reachable = [False] * N
    stack = [Y]
    while stack:
        u = stack.pop()
        if reachable[u]:
            continue
        reachable[u] = True
        for p in dag_rev[u]:
            if not reachable[p]:
                stack.append(p)

    # ---- Step D: Sweep-line events ----
    # event = (pos, type, data)
    # type: 0=IN, 1=QUERY, 2=OUT
    events = []

    # Vertex point contributions at time dist[u]
    for u in range(N):
        if reachable[u]:
            events.append((dist[u], 0, -1))  # IN
            events.append((dist[u], 2, -1))  # OUT

    # Edge interior range contributions
    for u in range(N):
        du = dist[u]
        if du >= INF:
            continue
        for v, w in adj[u]:
            # Directed shortest edge u -> v
            if du + w == dist[v] and reachable[v]:
                L = du + 1
                R = dist[v] - 1
                if L <= R:
                    events.append((L, 0, -1))  # IN
                    events.append((R, 2, -1))  # OUT

    # Queries at time dist[k]
    for k in range(N):
        if reachable[k]:
            events.append((dist[k], 1, k))

    # Sort so IN(0) before QUERY(1) before OUT(2) at same position
    events.sort()

    ans = [0] * N
    balance = 0
    for pos, typ, dat in events:
        if typ == 0:
            balance += 1
        elif typ == 1:
            ans[dat] = balance
        else:
            balance -= 1

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


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