D. Отказ от дорог
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Codefortia это маленькое островное государство, расположенное где-то в западной части Тихого океана. Оно состоит из $$$n$$$ поселений, соединенных $$$m$$$ двусторонними дорогами из гравия. Любопытно, что верования жителей требуют, чтобы время, необходимое для прохода по каждой дороге было равно $$$a$$$ или $$$b$$$ секунд. Гарантируется, что из любого поселения можно добраться до любого другого, пользуясь только дорогами из гравия.

Codefortia не так давно столкнулась с финансовым кризисом. Таким образом, король решил отказаться от некоторых дорог так, чтобы:

  • было возможно добраться из любого поселения до любого другого, пользуясь только оставленными дорогами,
  • сумма времен, которые требуются для проезда по каждой дороге, должна быть минимально возможной (другими словами, оставленные дороги должны образовывать минимальное остовное дерево, используя время, которое требуется для проезда по дороге как ее вес),
  • среди всех планов, которые минимизируют описанную выше сумму, время, которое нужно, для путешествия от королевской резиденции (в поселении $$$1$$$) до дома парламента (в поселении $$$p$$$) используя только оставленные дороги, должно быть минимально возможно.

К сожалению, король забыл, где находится дом парламента Для каждого поселения $$$p = 1, 2, \dots, n$$$, можете ли вы сказать, за какое минимальное время король может проехать от королевской резиденции до дома парламента (расположенном в поселении $$$p$$$), после отказа от некоторых дорог, по правилам описанным выше?

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

В первой строке записано четырые целых числа $$$n$$$, $$$m$$$, $$$a$$$ and $$$b$$$ ($$$2 \leq n \leq 70$$$, $$$n - 1 \leq m \leq 200$$$, $$$1 \leq a < b \leq 10^7$$$) — количество поселений и дорог из гравия в Codefortia, и два возможных времен проезда.

В следующих строках записано по три целых числа $$$u, v, c$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$, $$$c \in \{a, b\}$$$), описывающих дорогу из гравия между поселениями $$$u$$$ и $$$v$$$, для проезда по которой требуется $$$c$$$ минут.

Гарантируется, что система дорог связна и не имеет петель и кратных ребер.

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

Выведите одну строку, содержащую $$$n$$$ целых чисел. $$$p$$$-е из них должно содержать минимальное время, которое нужно для проезда из $$$1$$$ в $$$p$$$, после отказа от выбранных дорог. Обратите внимание, что для разных $$$p$$$ вам может быть нужно отказаться от разных наборов дорог.

Примеры
Входные данные
5 5 20 25
1 2 25
2 3 25
3 4 20
4 5 20
5 1 20
Выходные данные
0 25 60 40 20
Входные данные
6 7 13 22
1 2 13
2 3 13
1 4 22
3 4 13
4 5 13
5 6 13
6 1 13
Выходные данные
0 13 26 39 26 13
Примечание

Минимальное возможное время проездов по дорогам в первом примере равно $$$85$$$ — следует отказаться ровно от одной дороги, время проезда по которой равно $$$25$$$. Обратите внимание, что после отказа от одной из этих дорог, становится невозможно проехать от поселения $$$1$$$ до поселения $$$3$$$ за время $$$50$$$.