2214: 最少能量
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：1
Solved：1
Description
飞飞昨晚做了一个很有意思的梦，他和他的好朋友壮壮进入了一个地图游戏。地图中有 N 个结点，有 M 条双向道路连接这些结点， 结点按照 1 ~ N 编号。刚开始飞飞在 1 号结点，壮壮在 2 号结点，他们要一起到 N 号结点去。
飞飞花费 B 的能量可以从一个结点走到相邻的结点，壮壮花费 E 的能量可以从一个结点走到相邻的结点。如果中途他俩走到同一个结点时，好兄弟一辈子，飞飞可以选择抱起壮壮一起走，这样需要花费 P 的能量可以从一个结点走到相邻的结点。当然了，如果 P < B + E，他们一起走可以更省力些，否则，他俩还是决定各走各的。
梦醒时分，飞飞感觉这个梦很好玩，他想让你帮忙计算最后他俩走到 N 点需要的最少能量。
Input
第一行输入 5 个正整数，分别是 B，E，P，N，M。
接下来M行输入两个整数，每行代表一条双向道路。
Output
输出他俩到 N 的最少能量
Sample Input Copy
4 4 5 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8Sample Output Copy
22HINT
样例说明 飞飞从 1 号结点走到 4 号结点花费能量 4，壮壮从 2 号结点走到 3 号结点再走到 4 号结点，花费 8 的能量，然后他俩一起从 4 到 7 到 8，花费 10 的能量，所以总共需 要的最少能量是 4+8+10=22。
数据规模 1<=M,B,E,P<=40000。3 <= N <= 40000。