Abandoning Roads

Description:

Input:

The first line of the input contains four integers $$$n$$$, $$$m$$$, $$$a$$$ and $$$b$$$ ($$$2 \leq n \leq 70$$$, $$$n - 1 \leq m \leq 200$$$, $$$1 \leq a < b \leq 10^7$$$) — the number of settlements and gravel roads in Codefortia, and two possible travel times. Each of the following lines contains three integers $$$u, v, c$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$, $$$c \in \{a, b\}$$$) denoting a single gravel road between the settlements $$$u$$$ and $$$v$$$, which requires $$$c$$$ minutes to travel.

You can assume that the road network is connected and has no loops or multiedges.

Output:

Output a single line containing $$$n$$$ integers. The $$$p$$$-th of them should denote the minimum possible time required to travel from $$$1$$$ to $$$p$$$ after the selected roads are abandoned. Note that for each $$$p$$$ you can abandon a different set of roads.

Sample Input:

5 5 20 25
1 2 25
2 3 25
3 4 20
4 5 20
5 1 20

Sample Output:

0 25 60 40 20

Sample Input:

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

Sample Output:

0 13 26 39 26 13

Note:

The minimum possible sum of times required to pass each road in the first example is $$$85$$$ — exactly one of the roads with passing time $$$25$$$ must be abandoned. Note that after one of these roads is abandoned, it's now impossible to travel between settlements $$$1$$$ and $$$3$$$ in time $$$50$$$.