CF1915G Bicycles

给定 $n$ 个城市和 $m$ 条连接两个城市 $u_i$ 和 $v_i$ 的双向道路，长度为 $w_i$。 现在城市 $n$ 举办了一场派对，住在城市 $1$ 的 Slavic 想要去参加。在城市之间往返需要骑自行车，而 Slavic 没有自行车，所以他需要在这些城市里购买自行车以赶到城市 $n$。 从 $1$ 到 $n$ 的每个城市 $j$ 里都有且仅有一辆自行车可供购买，每辆自行车的速度系数为 $s_j$。 当 Slavic 骑上编号为 $j$ 的自行车后，他可以在任何时刻和任何地点通过一条道路 $i$，花费 $w_i\times s_j$ 的时间。 求 Slavic 骑车从城市 $1$ 赶到城市 $n$ 参加派对所需的最短时间。

第一行包含一个整数 $ t\, ( 1 \leq t \leq 100 )$，代表测试数据组数。 每组数据的第一行包含两个整数 $n$ 和 $m$，代表城市的数量和道路的数量。 接下来的 $m$ 行中，第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $w_i$，代表一条连接城市 $u_i$ 和 $v_i$，长度为 $w_i$ 的双向道路。 每组数据的最后一行包含 $n$ 个整数 $ s_1, \ldots, s_n $，代表在城市 $i$ 可供购买的自行车的速度系数。

对于每组测试数据，输出一个整数，代表从城市 $1$ 到达城市 $n$ 所需的最短时间。

$ 2 \leq n \leq 1000 $，$ n - 1 \leq m \leq 1000$，$ 1 \leq s_i \leq 1000 $； $ 1 \le u_i, v_i \le n $ , $ u_i \neq v_i $，$ 1 \leq w_i \leq 10^5$； 所有测试数据的 $\sum n$、$\sum m$ 不超过 $1000$。 保证存在方案能从城市 $1$ 到达城市 $n$。 By Misaka16172