Berland有n个城市,首都位于城市s,总统的历史故乡位于城市t(s≠t)。城市之间通过单向道路连接,每条道路的行驶时间均为正整数。
总统每年都会访问一次他的历史故乡 t,为此,他的车队会经过从 s 到 t 的一些路径(他总是乘坐私人飞机返回)。由于总统是一个非常忙碌的人,他总是选择从 s 到 t 的路径,沿着这条路径他会走得最快。
公路和铁道部希望了解每一条道路:总统出访期间是否一定会经过它,如果没有,是否有可能对其进行修复,使其一定会被纳入从首都到总统历史故乡的最短路径中。显然,这条路无法修好,所以路上的行驶时间不到一小时。 Berland 部门与其他部门一样,对维持预算感兴趣,因此想知道修复道路的最低成本。此外,它非常注重准确性,因此它会修复道路,使道路上的行驶时间始终为正整数。
输入
第一行包含四个整数 n、m、s 和 t (2 ≤ n ≤ 105; 1 ≤ m ≤ 105; 1 ≤ s, t ≤ n) — Berland 的城市和道路数量、首都和总统家乡的数量 (s ≠ t)。
接下来的 m 行包含道路。每条道路均以三个整数 ai、bi、li 的形式给出(1 ≤ ai,bi ≤ n;ai ≠ bi;1 ≤ li ≤ 106)——第 i 条道路连接的城市以及沿该道路骑行所需的时间。道路是从ai市直达bi市的。
城市编号为 1 到 n。每对城市之间可以有多条道路。保证沿路有一条从 s 到 t 的路径。
输出
打印 m 行。第 i 行应包含有关第 i 条道路的信息(道路按照输入中出现的顺序进行编号)。
如果总统在旅行期间肯定会沿着这条路骑行,则该行必须包含一个单词“YES”(不带引号)。
否则,如果第i条路可以修复,使其行驶时间保持为正,那么总统肯定会沿着它骑行,打印空格分隔的单词“CAN”(不带引号),以及修复的最低成本。
如果我们不能让总统一定会沿着它骑行,请打印“NO”(不带引号)。
示例
输入 #1
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
输出 #1
YES CAN 2 CAN 1 CAN 1 CAN 1 CAN 1 YES
输入 #2
3 3 1 3 1 2 10 2 3 10 1 3 100
输出 #2
YES YES CAN 81
输入 #3
2 2 1 2 1 2 1 1 2 2
输出 #3
YES NO
注意
修路成本是修路前后骑行时间的差值。
在第一个样本中,总统最初可以选择以下两种方式之一乘坐:1 → 2 → 4 → 5 → 6 或 1 → 2 → 3 → 5 → 6。