题目描述

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

Among $\frac{n(n-1)}{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$ .

【简要题意】

给定一张 $n$ 个点的完全图, 边都是无向的。

一共有 $\frac{n(n-1)}{2}$ 条边, 其中有 $m$ 条边的边权是 $a$ , 剩下的边边权 都是 $b$。

求 $1$ 到 $n$ 的最短路。

$2 \leq n \leq 100000,0 \leq m \leq 500000$

输入格式

The input consists of multiple tests. For each test:

The first line contains $4$ integers $n, m, a, b\left(2 \leq n \leq 10^{5}, 0 \leq m \leq 5 \cdot 10^{5}, 1 \leq a, b \leq 10^{9}\right)$ . Each of the following $m$ lines contains $2$ integers $u_{i}, v_{i}$, which denotes cities $u_{i}$ and $v_{i}$ are connected by highway. $( \left.1 \leq u_{i}, v_{i} \leq n, u_{i} \neq v_{i}\right)$

输出格式

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

样例输入输出

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

2
3