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:

  it will be possible to travel between each pair of cities using the remaining roads only,  the sum of times required to pass each remaining road will be minimum possible (in other words, remaining roads must form minimum spanning tree, using the time to pass the road as its weight),  among all the plans minimizing the sum of times above, the time required to travel between the king's residence (in settlement $1$) and the parliament house (in settlement $p$) using the remaining roads only will be minimum possible. 

The king, however, forgot where the parliament house was. For each settlement $p = 1, 2, \dots, 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?


-----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.


-----Examples-----
Input
5 5 20 25
1 2 25
2 3 25
3 4 20
4 5 20
5 1 20

Output
0 25 60 40 20

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

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$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import heapq\nn,m,a,b=map(int,input().split())\ngraph={i:[] for i in range(n)}\nfor i in range(m):\n    u,v,w=map(int,input().split())\n    graph[u-1].append((v-1,w))\n    graph[v-1].append((u-1,w))\ncomponents=[-1]*n\ncomp=-1\nfor i in range(n):\n    if components[i]==-1:\n        comp+=1\n        components[i]=comp\n        prev=[]\n        layer=[i]\n        while layer!=[]:\n            newlayer=[]\n            for guy in layer:\n                for guy1 in graph[guy]:\n                    if guy1[1]==a and components[guy1[0]]==-1:\n                        newlayer.append(guy1[0])\n                        components[guy1[0]]=comp\n            prev=layer[:]\n            layer=newlayer[:]\nuseless=[]\nfor guy in graph:\n    for neigh in graph[guy]:\n        if components[guy]==components[neigh[0]] and neigh[1]==b:\n            useless.append((guy,neigh))\nfor guy in useless:\n    graph[guy[0]].remove(guy[1])\ncounts=[0]*(comp+1)\nfor i in range(n):\n    counts[components[i]]+=1\nbad=[]\nfor i in range(comp+1):\n    if counts[i]<=3:\n        bad.append(i)\n        for j in range(n):\n            if components[j]==i:\n                components[j]=-1\nfor guy in bad[::-1]:\n    for i in range(n):\n        if components[i]>guy:\n            components[i]-=1\ncomp-=len(bad)\ncomp+=1\ndists=[[float("inf") for i in range(2**comp)] for j in range(n)]\ndists[0][0]=0\npq=[]\nheapq.heappush(pq,[0,0,0])\nremaining=n\nvisited=[0]*n\nwhile len(pq)>0 and remaining>0:\n    dist,vert,mask=heapq.heappop(pq)\n    if visited[vert]==0:\n        visited[vert]=1\n        remaining-=1\n    for neigh in graph[vert]:\n        if neigh[1]==b:\n            if components[vert]==components[neigh[0]] and components[vert]!=-1:\n                continue\n            if components[neigh[0]]!=-1:\n                if mask & (2**components[neigh[0]])>0:\n                    continue\n            if components[vert]!=-1:\n                maskn=mask+2**(components[vert])\n            else:\n                maskn=mask\n        else:\n            maskn=mask\n        if dist+neigh[1]<dists[neigh[0]][maskn]:\n            dists[neigh[0]][maskn]=dist+neigh[1]\n            heapq.heappush(pq,[dist+neigh[1],neigh[0],maskn])\noptimal=[str(min(dists[i])) for i in range(n)]\nprint(" ".join(optimal))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14957