测试数据来自 system/2196

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小贝和小丽在不同的路口，他们希望花费最小的能量返回学校。从一个路口走到一个相连路口，小贝要花费 \(A\) 单位的能量，小丽要花费 \(B\) 单位的能量。

　　如果某次他们两走到同一个路口，小贝可以背着小丽走路，花费 \(C\) 单位的能量走到另外一个相连的路口。当然，存在 \(P>B+E\) 的情况。相遇后，他们可以一直背着走，也可以独立分开。

　　已知共有N个路口（编号1..N），有M条双向道路连接这些路口，其中小贝的起点是1，小丽的起点是2，学校所在的路口为 \(N\)。

【输入格式】

　　第 1 行包含五个整数：\(A, B, C, N\) 和 \(M\)，\(A,B,C\) 的意义如题目描述，\(N\) 表示路口数量，\(M\) 表示路口间道路数量。
　　接下来的 \(M\) 行，每行表示一条道路连接的路口，道路是双向的。

【输出格式】

　　一个整数，表示最小能量。

【输入输出样例】

　Input

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

　Output

22

【输入输出样例解释】

　　小贝从 1->4，小丽从 2->3->4，在4处相遇后小贝背着小丽从 4->7->8。

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤A,B,C,N,M≤40000\).

【来源】

　　Mr.he