题目描述

Berland 有 $n$ 个城市，首都位于城市 $s$，总统的故乡位于城市 $t$（$s\neq t$）。这些城市通过若干有向道路相连，每条道路的通行时间为一个正整数。

每年一次，总统会回到他的故乡 $t$，他会选择一条从 $s$ 到 $t$ 的路径出发（他总是坐私人飞机返回）。由于总统工作繁忙，他总是选择从 $s$ 到 $t$ 所需时间最短的路径。

公路与铁路部想要了解每一条道路的以下情况：总统是否一定会经过这条道路；如果不会，是否有可能通过修路让这条道路一定包含在最短路径中。显然，道路的维修不能让其通行时间小于 1。Berland 的政府希望尽量节约预算，因此希望知道维修这条道路所需的最小代价。同时，政府对精度要求极高，所以道路修理后通行时间仍为正整数。

输入格式

第一行包含四个整数 $n$、$m$、$s$ 和 $t$——城市数、公路数、首都编号与总统故乡编号（$s\neq t$）。

接下来 $m$ 行，每行三个整数 $a_i, b_i, l_i$ ，表示第 $i$ 条道路从 $a_i$ 指向 $b_i$，通行时间为 $l_i$。

城市编号为 $1$ 到 $n$。同一对城市之间可以有多条道路。保证存在从 $s$ 到 $t$ 的路径。

输出格式

输出 $m$ 行。第 $i$ 行对应输入中的第 $i$ 条道路。

如果总统在他的出行中一定会经过这条道路，输出 "YES"（不带引号）。

否则，如果可以通过维修使得该道路通行时间仍为正且大总统出行一定会经过，输出 "CAN"（不带引号）以及所需最小维修费用（用空格分隔）。

如果无法使总统一定经过该道路，输出 "NO"（不带引号）。

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

YES
CAN 2
CAN 1
CAN 1
CAN 1
CAN 1
YES

3 3 1 3
1 2 10
2 3 10
1 3 100

YES
YES
CAN 81

2 2 1 2
1 2 1
1 2 2

YES
NO

说明 / 提示

修路的费用为修前后通行时间之差。

在第一个样例中，总统最初可以选择两条路径：$1\rightarrow2\rightarrow4\rightarrow5\rightarrow6$ 或 $1\rightarrow2\rightarrow3\rightarrow5\rightarrow6$。

由 ChatGPT 5 翻译

数据范围

（$2 \leq n \leq 10^{5}; 1 \leq m \leq 10^{5}; 1 \leq s,t \leq n$）

（$1 \leq a_i, b_i \leq n; a_i \ne b_i; 1 \leq l_i \leq 10^6$）