Intercity

Time limit3sMemory limit128 MB

Summary

Find the cheapest fare from city 1 to city N in a complete graph where K given edges cost A and all other edges cost B.

Level: Medium7 of 10
Topics: Shortest path, Graph, BFS
Solved: No attempts yet

Problem

A few years ago the Ukrainian railway system was very convenient. Between any two cities ran one direct train, and anyone could pay $B$ hryvnia to travel from the city they were in to the city they wanted to reach.

Recently a lot of new trains were launched. Each new train replaced one old train, and its fare was set to $A$ hryvnia. So between any pair of cities there is still exactly one direct train, either new or old. Every train runs in both directions, and the fare does not depend on the direction.

Ukraine has $N$ large cities and you live in city 1. You want to reach city $N$ as cheaply as possible. The number of transfers does not matter.

Input

The first line contains four integers $N$ , $K$ , $A$ , $B$ ( $2 \le N \le 500000$ , $0 \le K \le 500000$ , $1 \le A, B \le 500000$ ): the number of cities, the number of new trains, the fare of a new train and the fare of an old train.

Each of the next $K$ lines contains two integers $u_i$ and $v_i$ ( $1 \le u_i, v_i \le N$ ), meaning that a new train runs between city $u_i$ and city $v_i$ . $u_i$ and $v_i$ are different, and every pair of cities appears at most once.

Output

Print the fare $P$ of the cheapest way to get from city 1 to city $N$ .

Examples2

Example 1
Input
```
5 4 1 4
1 2
2 3
2 4
3 5
```
Expected output
```
3
```
Example 2
Input
```
6 5 1 100
1 2
2 3
3 4
4 5
5 6
```
Expected output
```
5
```