#P1274. Travel
Travel
题目描述
The country frog lives in has towns which are conveniently numbered by .
Among pairs of towns, of them are connected by bidirectional highway, which needs minutes to travel. The other pairs are connected by railway, which needs minutes to travel.
Find the minimum time to travel from town to town .
【简要题意】
给定一张 个点的完全图, 边都是无向的。
一共有 条边, 其中有 条边的边权是 , 剩下的边边权 都是 。
求 到 的最短路。
输入格式
The input consists of multiple tests. For each test:
The first line contains 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 lines contains integers , which denotes cities and are connected by highway. $( \left.1 \leq u_{i}, v_{i} \leq n, u_{i} \neq v_{i}\right)$
输出格式
For each test, write integer which denotes the minimum time.
样例输入输出
3 2 1 3
1 2
2 3
3 2 2 3
1 2
2 3
2
3