完整的测试数据和题面

问题描述

一个国家有N座城市，城市编号1到N。这些城市由M条双向高速路连接了起来。
何老板和nodgd两人相约去N号城市旅行。
何老板骑摩托车从1号城市出发，nodgd开卡车从2号城市出发。
何老板骑车每经过一条高速路都要消耗A升汽油，nodgd开卡车每经过一条高速路要消耗B升汽油。
如果两人在某个城市相遇了，何老板就会把摩托车装载在nodgd的卡车上，然后何老板坐上nodgd的卡车，一起行走，这样每经过一条高速路需要消耗C升汽油。求他们到达N号城市，最少需要消耗汽油的总量？

输入格式

第一行,五个空格以间隔的整数A, B, C, N, M
接下来M行每行两个数 X,Y 表示有一条高速公路连接编号X和Y的两个城市 (1<=X,Y<=n)

输出格式

一个整数，表示最少消耗的汽油总量。

样例输入

4 4 5 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8

样例输出

22

提示
A,B,C,N,M<=50,000