题目描述
【题目描述】
“猴通快递”最近拓展了公司的业务线，希望能更好的服务猴城的客户。
猴城的地图可以简略地用n个点，m条边的无向图表示，其中结点从1到n进行编号。目前“猴通快递”的物流仓库一共有两个，分别位于编号为1、2的两个结点。现在两个仓库需要分别发一辆车把包裹运送到n号结点。为了节省成本，公司希望找到发送包裹的最小成本。
每次从一个区域走到另一个区域时，一号仓库的车运送的成本为B，二号仓库的车运送的成本为E。
如果两个仓库的车走到了同一个区域，它们可以把包裹放到同一辆车上一起运送，此时运送所有包裹前往另一个相连的区域的代价为P。(P也可以大于B+E)
两辆车相遇后，包裹可以一起运送，也可以分别运送。
【输入格式】
输入的第一行包含正整数B, E, P, n和m。(所有数字<=40000)。n是猴城的地点数量（n 3n≥3），m为区域间路的数量。
第22 ~ m+1行，每行两个数。表示一条双向边所连接的两个地点，题目保证有解。
【输出格式】
一个整数代表运送包裹的最小成本。
【输入样例#1】
4 4 5 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8
【输出样例#1】
22