### 问题描述 小齐和她的妹妹艾尔希在白天在不同的牧场吃草，晚上她们都想回到谷仓休息。作为聪明的奶牛，她们制定了一个计划，以最小化她们共同步行时花费的总能量。 当小齐从一个牧场走到相邻的牧场时，她需要花费 $B$ 单位的能量，而艾尔希在相邻的牧场之间需要花费 $E$ 单位的能量。然而，如果小齐和艾尔希在同一片牧场，小齐可以背着艾尔希，这样在共同移动到相邻的牧场时只需花费 $P$ 单位的能量（其中 $P$ 可能远小于 $B+E$，即小齐和艾尔希分别独立步行的总能量）。顺便说一下，小齐和艾尔希对“背着”这个词并不满意，因为她们不明白为什么农场上的猪应该因为这种卓越的交通方式而获得所有的赞誉。 给定 $B$、$E$ 和 $P$，以及农场的布局，请计算小齐和艾尔希到达谷仓所需的最小能量。 ### 输入格式 第 $1$ 行：两个整数 $N$ 和 $Q$。 输入的第一行包含正整数 $B$、$E$、$P$、$N$ 和 $M$，它们都不超过 40,000。其中，$B$、$E$ 和 $P$ 如上所述，$N$ 是农场的牧场数量（编号为 1 到 $N$，其中 $N \geq 3$），$M$ 是牧场之间的连接数量。小齐和艾尔希分别从牧场 $1$ 和 $2$ 开始，谷仓位于牧场 $N$。 接下来的 $M$ 行描述了牧场之间的连接，由两个字段的整数索引指定。连接是双向的。在沿一系列这样的连接从牧场 $1$ 到牧场 $N$，以及从牧场 $2$ 到牧场 $N$ 的情况下，总是可以到达。 ### 输出格式 输出一个整数，表示小齐和艾尔希共同到达谷仓所需的最小能量。在给定示例中，小齐从 $1$ 到 $4$，艾尔希从 $2$ 到 $3$ 再到 $4$，然后，她们一起从 $4$ 到 $7$ 再到 $8$。 ### 样例输入 ``` 4 4 5 8 8 1 4 2 3 3 4 4 7 2 5 5 6 6 8 7 8 ``` ### 样例输出 ``` 22 ``` ### 评测数据规模 $1 \leq B,E,P \leq 40,000$。