E. Президент и дороги
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии n городов, столица находится в городе s, а историческая родина Президента — в городе t (s ≠ t). Города соединены односторонними дорогами, время проезда по каждой из дорог — целое положительное число.

Раз в год Президент посещает свою историческую родину t, для чего его кортеж проезжает по некоторому пути из s в t (обратно он всегда возвращается на личном самолете). Так как Президент — очень занятой человек, то он всегда выбирает путь из s в t, по которому он проедет быстрее всего.

Министерство дорог и путей сообщения хочет узнать для каждой дороги: обязательно ли проедет по ней Президент во время своего путешествия, и если нет, то возможно ли её починить так, чтобы она в любом случае входила в кратчайший путь из столицы в историческую родину Президента. Очевидно, что дорогу невозможно починить так, чтобы время проезда по ней стало меньше единицы. Министерство Берляндии, как и любое другое, заинтересовано в сохранении бюджета, поэтому оно хочет узнать минимальную стоимость починки дороги. Также оно очень любит точность, поэтому ремонтирует дороги так, что время проезда по ним всегда остаётся целым числом.

Входные данные

В первой строке записаны четыре целых числа n, m, s и t (2 ≤ n ≤ 105; 1 ≤ m ≤ 105; 1 ≤ s, t ≤ n) — количество городов и дорог в Берляндии, номера столицы и исторической родины Президента (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» (без кавычек).

Примеры
Входные данные
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 → 2 → 4 → 5 → 6 либо 1 → 2 → 3 → 5 → 6.