AT_past202010_j ワープ

有 $n$ 个城市（编号 $1$ 到 $n$）和 $m$ 条道路（编号 $1$ 到 $m$）。第 $i$ 条道路双向连接 $a_i$ 和 $b_i$，分值为 $c_i$。你每走过一条路，就会加上这条路的分值。 同时还有 A,B,C 三种类型的传送门，$i$ 市的传送门的类型为 $s_i$。使用时，传送门的起终点必须是不同类型的传送门。 - 当你使用 A 和 B 两种传送门时，获得 $x_{AB}$ 分； - 当你使用 A 和 C 两种传送门时，获得 $x_{AC}$ 分； - 当你使用 B 和 C 两种传送门时，获得 $x_{BC}$ 分。 请问：从 $1$ 市到 $n$ 市，最少的分值是多少？

输入以以下格式从标准输入读入。 >$n$ $m$ > >$x_{AB}$ $x_{AC}$ $x_{BC}$ > >$s_1s_2...s_n$ > >$a_1$ $b_1$ $c_1$ > >$a_2$ $b_2$ $c_2$ > >... > >$a_m$ $b_m$ $c_m$

一个整数，最小总分值。数据保证没有重边，且一定有至少一种从 $1$ 市到 $n$ 市的方法。

$2 \le n \le 10^5$，$1 \le m \le 10^5$； $1 \le x_{AB},x_{AC},x_{BC} \le 10^9$； $1 \le a_i,b_i \le n$，$a_i \neq b_i$，$1 \le c_i \le 10^9$。