QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB
[0]

# 3704. Travel

Statistics

The country frog lives in has n towns which are conveniently numbered by 1,2,,n.

Among n(n1)2 pairs of towns, m of them are connected by bidirectional highway, which needs a minutes to travel. The other pairs are connected by railway, which needs b minutes to travel.

Find the minimum time to travel from town 1 to town n.

Input

The input consists of multiple tests. For each test:

The first line contains 4 integers n,m,a,b (2n105,0m5105,1a,b109). Each of the following m lines contains 2 integers ui,vi, which denotes cities ui and vi are connected by highway. (1ui,vin,uivi).

Output

For each test, write 1 integer which denotes the minimum time.

Sample Input

3 2 1 3
1 2
2 3
3 2 2 3
1 2
2 3

Sample Output

2
3