题目描述

给定 $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$ 所需的最短时间。

样例

3
5 5
1 2 2
3 2 1
2 4 5
2 5 7
4 5 1
5 2 1 3 3
5 10
1 2 5
1 3 5
1 4 4
1 5 8
2 3 6
2 4 3
2 5 2
3 4 1
3 5 8
4 5 2
7 2 8 4 1
7 10
3 2 8
2 1 4
2 5 7
2 6 4
7 1 2
4 3 5
6 4 2
6 7 1
6 7 4
4 5 9
7 6 5 4 3 2 1

19
36
14

样例说明

$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

来源

Codeforces 1915G，英文题名 Bicycles。