题目描述

给出一个有向图，从起点走到终点（必须走最短路），问一条边是否一定会被经过。如果不一定经过它，可以让它的边权减少多少，使得一定经过它（边权不能减少到 $0$），如果可以的话，要使减少的边权最小。

输入格式

第一行四个整数 $n,m,s,t$，依次表示顶点数、边数、起点、终点，$2\le n\le 10^{5}$，$1\le m\le 10^{5}$，$s≠t$。

接下来 $m$ 行，每行三个整数 $a_i,b_i,l_i$，描述一条边，$a_{i}≠b_{i}$，$1\le l_{i}\le 10^{6}$$。

输出格式

输出 $m$ 行，第 $i$ 行对应第 $i$ 条边的答案。如果必须经过，则输出 YES；如果可以通过减少边权使得它必须经过，则输出 CAN k，其中 $k$ 表示边权要减少的最小值；否则输出 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