B"Codefortia is a small island country located somewhere in the West Pacific. It consists of n settlements connected by m bidirectional gravel roads. Curiously enough, the beliefs of the inhabitants require the time needed to pass each road to be equal either to a or b seconds. It's guaranteed that one can go between any pair of settlements by following a sequence of roads. Codefortia was recently struck by the financial crisis. Therefore, the king decided to abandon some of the roads so that: The king, however, forgot where the parliament house was. For each settlement p = 1, 2, ... , n , can you tell what is the minimum time required to travel between the king's residence and the parliament house (located in settlement p ) after some roads are abandoned? The first line of the input contains four integers n , m , a and b ( 2 <= q n <= q 70 , n - 1 <= q m <= q 200 , 1 <= q a < b <= q 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 <= q u, v <= q 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 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. 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 . "...