P3110 [USACO14DEC] Piggy Back S

Bessie 和 Elsie 在不同的区域放牧，他们希望花费最小的能量返回谷仓。从一个区域走到一个相连区域，Bessie 要花费 $B$ 单位的能量，Elsie要花费 $E$ 单位的能量。 如果某次他们两走到同一个区域，Bessie 可以背着 Elsie 走路，花费 $P$ 单位的能量走到另外一个相连的区域。当然，存在 $P>B+E$ 的情况。 相遇后，他们可以一直背着走，也可以独立分开。 Bessie 从 $1$ 号区域出发，Elsie 从 $2$ 号区域出发，两个人都要返回到位于 $n$ 号区域的谷仓。

第一行输入 5 个整数 $B,E,P,n,m$。$B,E,P$ 的含义如上文所述。 $n$ 表示农场中区域的数量，$m$ 表示连接两个区域的道路的数量。 接下来 $m$ 行，每行两个整数 $x,y$，描述一条 $x$ 区域和 $y$ 区域之间的双向边。数据保证图是连通的。

一行一个整数，表示 Bessie 和 Elsie 能量花费总和的最小值。

$1 \leq B,E,P,n,m \leq 4 \times 10^4$。 #### 样例解释： Bessie 从 1 走到 4，Elsie 从 2 走到 3 再走到 4。然后，两个人一起从 4 走到 7，再走到 8。