President and Roads
Contest: Codeforces Round #Pi (Div. 2)
Difficulty rating: 2200
Tags: dfs and similar, graphs, hashing, shortest paths

Berland has n cities, the capital is located in city s, and the historic home town of the President is in city t (s ≠ t). The cities are connected by one-way roads, the travel time for each of the road is a positive integer.

Once a year the President visited his historic home town t, for which his motorcade passes along some path from s to t (he always returns on a personal plane). Since the president is a very busy man, he always chooses the path from s to t, along which he will travel the fastest.

The ministry of Roads and Railways wants to learn for each of the road: whether the President will definitely pass through it during his travels, and if not, whether it is possible to repair it so that it would definitely be included in the shortest path from the capital to the historic home town of the President. Obviously, the road can not be repaired so that the travel time on it was less than one. The ministry of Berland, like any other, is interested in maintaining the budget, so it wants to know the minimum cost of repairing the road. Also, it is very fond of accuracy, so it repairs the roads so that the travel time on them is always a positive integer.

Input format:
The first lines contain four integers n, m, s and t (2 ≤ n ≤ 105; 1 ≤ m ≤ 105; 1 ≤ s, t ≤ n) — the number of cities and roads in Berland, the numbers of the capital and of the Presidents' home town (s ≠ t).

Next m lines contain the roads. Each road is given as a group of three integers ai, bi, li (1 ≤ ai, bi ≤ n; ai ≠ bi; 1 ≤ li ≤ 106) — the cities that are connected by the i-th road and the time needed to ride along it. The road is directed from city ai to city bi.

The cities are numbered from 1 to n. Each pair of cities can have multiple roads between them. It is guaranteed that there is a path from s to t along the roads.

Output format:
Print m lines. The i-th line should contain information about the i-th road (the roads are numbered in the order of appearance in the input).

If the president will definitely ride along it during his travels, the line must contain a single word "YES" (without the quotes).

Otherwise, if the i-th road can be repaired so that the travel time on it remains positive and then president will definitely ride along it, print space-separated word "CAN" (without the quotes), and the minimum cost of repairing.

If we can't make the road be such that president will definitely ride along it, print "NO" (without the quotes).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The cost of repairing the road is the difference between the time needed to ride along it before and after the repairing.

In the first sample president initially may choose one of the two following ways for a ride: 1 → 2 → 4 → 5 → 6 or 1 → 2 → 3 → 5 → 6.

Example input:
6 7 1 6
1 2 2
1 3 10
2 3 7
2 4 8
3 5 3
4 5 2
5 6 1

Example output:
YES
CAN 2
CAN 1
CAN 1
CAN 1
CAN 1
YES

Example input:
3 3 1 3
1 2 10
2 3 10
1 3 100

Example output:
YES
YES
CAN 81

Editorial:
At first, let's find edges that do not belong to any shortest paths from s to t. Let's find two shortest path arrays d1 and d2 with any shortest-path-finding algorithm. First array stores shortest path length from s, and the second — from t. Edge (u, v) then will be on at least one shortest path from s to t if and only if d1[u] + w(u, v) + d2[v] == d1[t].
Let's build shortest path graph, leaving only edges described above. If we consider shortest path from s to t as segment [0..D] and any edge (u, v) in shortest path graph as its subsegment [d1[u]..d1[v]], then if such subsegment do not share any common point with any other edge subsegment, except its leftest and rightest point (d1[u] and d1[v]), this edge belongs to every shortest path from s to t.
Now we could surely answer «YES» to such edges. Next part of the solution are much simple. If edge (u, v) do not belong to every shortest path, we could try decrease its weight. This edge will belong to every shortest path if and only if its weight will become d1[t] - d1[u] - d2[v] - 1. So, if this value are strictly positive, we should answer «CAN» considering new edge weight. Otherwise we need to output «NO».