Роджер и Трой играют в догонялки в Университете Ватерлоо. Университет Ватерлоо можно представить как $N$ зданий, соединенных $M$ тротуарами. $i$-й тротуар соединяет здания $a_i$ и $b_i$ и имеет длину $d_i$ метров. Между любой парой зданий существует не более одного тротуара. Тротуары не пересекаются (то есть переходить с одного тротуара на другой можно только в здании) и могут не лежать в одной плоскости (из-за мостов и туннелей). Из любого здания можно добраться до любого другого, передвигаясь по тротуарам.
Роджер начинает игру в здании 1 и может передвигаться со скоростью до $v_1$ метров в секунду. Роджер также может ждать в здании или в любой точке на тротуаре. Роджер будет двигаться так, чтобы максимизировать продолжительность игры в догонялки.
Трой выбирает здание $x$ и выпускает группу студентов из здания $x$. Студенты распространяются со скоростью $v_2$ метров в секунду по всем тротуарам. Игра в догонялки заканчивается, когда студенты Троя догоняют Роджера.
Для каждого здания $x$ определите, как долго продлится игра в догонялки.
Входные данные
Первая строка входных данных содержит 4 целых числа, разделенных пробелами: $N, M, v_1, v_2$ ($2 \le N \le 2000$; $N-1 \le M \le 5000$; $1 \le v_1, v_2 \le 100$).
Следующие $M$ строк содержат по 3 целых числа, где $i$-я строка содержит числа $a_i, b_i, d_i$ ($1 \le a_i < b_i \le N$; $1 \le d_i \le 10\,000$).
В следующей таблице показано распределение 25 баллов:
| Баллы | Дополнительные ограничения |
|---|---|
| 3 балла | $N = 3$ и $M = 2$. |
| 3 балла | $N = 3$ и $M = 3$. |
| 7 баллов | $v_1 = v_2 = 1$ и все тротуары имеют длину 2 метра ($d_i = 2$). |
| 7 баллов | $N \le 100$ и $M \le 200$. |
| 5 баллов | Нет. |
Выходные данные
Выведите $N-1$ строк, где $i$-я строка содержит продолжительность игры в догонялки в секундах, если Трой выпускает группу студентов из здания $i+1$. Вы должны вывести продолжительность в виде несократимой дроби.
Заметьте, что целое число $d$ является делителем целого числа $q$, если при делении $q$ на $d$ остаток равен нулю. Целое число $z$ является общим делителем целых чисел $x$ и $y$, если $z$ является делителем как $x$, так и $y$. Дробь $x/y$ является несократимой, если $y$ положительно, а $x$ и $y$ не имеют общего делителя больше единицы.
Примеры
Входные данные 1
3 2 1 10 1 2 135 1 3 15
Выходные данные 1
15/1 5/3
Примечание
Для $x = 2$ Роджеру следует идти к зданию 3. Через 15 секунд студенты догонят Роджера в здании 3, и игра закончится.
Для $x = 3$ Роджеру следует идти в сторону здания 2. Через $5/3$ секунды студенты догонят Роджера на тротуаре между зданиями 2 и 3, и игра закончится. Заметьте, что Роджер прошел $1.666\dots$ метров, а студенты прошли $15 + 1.666\dots$ метров.
Входные данные 2
4 4 1 1 1 2 2 1 3 2 2 3 2 1 4 2
Выходные данные 2
4/1 4/1 5/1
Примечание
Для $x = 2$ Роджеру следует идти к зданию 4.
Для $x = 3$ Роджеру следует идти к зданию 4.
Для $x = 4$ Роджеру следует идти к центру тротуара между зданиями 2 и 3.