6889: 阿宁去游玩
[Creator : ]
Description
阿宁打算下次放假去游玩。一共有 $n$ 个城市， 阿宁住在 $1$ 号城市，去到 $n$ 号城市游玩。
城市有两种属性，一种是炎热，另一种是酷寒，每个城市是其中一种。从一个城市前往另一个城市，如果要前往的城市和当前城市的属性相同，则需要 $x$ 时间，否则需要 $y$ 时间。
阿宁可以使用倒转膜法，该膜法可以使所有城市（除了阿宁当前所在的城市）的属性变化（炎热变酷寒，酷寒变炎热），花费 $z$ 时间。倒转膜法可以使用任意次。
阿宁想尽快去到 $n$ 号城市游玩，她想知道她最少需要多少时间到达目的地？
城市有两种属性，一种是炎热，另一种是酷寒，每个城市是其中一种。从一个城市前往另一个城市，如果要前往的城市和当前城市的属性相同，则需要 $x$ 时间，否则需要 $y$ 时间。
阿宁可以使用倒转膜法，该膜法可以使所有城市（除了阿宁当前所在的城市）的属性变化（炎热变酷寒，酷寒变炎热），花费 $z$ 时间。倒转膜法可以使用任意次。
阿宁想尽快去到 $n$ 号城市游玩，她想知道她最少需要多少时间到达目的地？
Input
第一行输入两个正整数 $n,m$，表示一共有 $n$ 个城市，$m$ 条道路。
第二行输入三个正整数 $x,y,z$，表示不同动作花费的时间。
第三行输入 $n$ 个正整数 $a_i$，表示第 $i$ 城市的属性，$0$ 表示炎热，$1$ 表示酷寒。
接下来 $m$ 行，每行输入两个正整数 $u,v$，表示 $u$ 号城市和 $v$ 号城市有道路相连。（道路是双向的，即 $u$ 能走到 $v$，$v$ 能走到 $u$）
第二行输入三个正整数 $x,y,z$，表示不同动作花费的时间。
第三行输入 $n$ 个正整数 $a_i$，表示第 $i$ 城市的属性，$0$ 表示炎热，$1$ 表示酷寒。
接下来 $m$ 行，每行输入两个正整数 $u,v$，表示 $u$ 号城市和 $v$ 号城市有道路相连。（道路是双向的，即 $u$ 能走到 $v$，$v$ 能走到 $u$）
保证 $1$ 号城市能到达 $n$ 号城市。
Output
一个整数，表示阿宁从 $1$ 号城市到达 $n$ 号城市所需要的最少时间。
Constraints
$2≤n≤2×10^5$
$1\leq m,x,y,z\leq 2 \times 10^5$
$1 \le u,v \le n$
$0\leq a_i\leq 1$
$1\leq m,x,y,z\leq 2 \times 10^5$
$1 \le u,v \le n$
$0\leq a_i\leq 1$
Sample 1 Input
5 6
1 3 9
1 0 0 1 1
1 2
1 3
2 3
2 4
3 4
4 5
Sample 1 Output
7
路径 $1\to 3\to 4\to 5$，花费时间为 $3+3+1=7$。
Sample 2 Input
3 3
1 10 2
0 1 1
1 2
1 3
2 3
Sample 2 Output
3
在 $1$ 号城市使用一次倒转膜法，路径 $1\to 3$，花费时间为 $2+1=3$。