题目描述

有 $n$ 座城市和 $m$ 条无向道路。道路 $i$ 连接城市 $u_i,v_i$，长度为 $w_i$。Slavic 从城市 $1$ 出发，要前往城市 $n$。

每座城市恰好出售一辆自行车。城市 $i$ 的自行车有一个慢度系数 $s_i$。Slavic 到达一座城市后可以免费购买那里的自行车，并且可以买任意多辆车。若他当前拥有编号为 $j$ 的自行车，骑这辆车经过一条长度为 $w$ 的道路需要 $w\times s_j$ 时间。

Slavic 起初没有自行车，不能步行；在城市 $1$ 买车后才能出发。求他从城市 $1$ 到城市 $n$ 的最短用时。

保证城市 $1$ 可以到达所有城市。

输入格式

第一行输入一个整数 $t$（$1 \le t \le 100$），表示测试用例组数。

每组测试数据的第一行输入两个整数 $n,m$（$2 \le n \le 1000$，$n-1 \le m \le 1000$），分别表示城市数和道路数。

接下来 $m$ 行，每行输入三个整数 $u_i,v_i,w_i$（$1 \le u_i,v_i \le n$，$u_i\ne v_i$，$1 \le w_i \le 10^5$），表示一条连接 $u_i,v_i$ 的无向道路。同一对城市之间可以有多条道路。

最后一行输入 $n$ 个整数 $s_1,s_2,\dots,s_n$（$1 \le s_i \le 1000$），表示每座城市出售的自行车慢度系数。

保证所有测试用例的 $n$ 之和和 $m$ 之和均不超过 $1000$。

输出格式

对每组测试数据输出一个整数，表示从城市 $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