题目描述

光头强的朋友们计划从他们居住的地方骑自行车去参加派对。除了光头强之外，他们所有人都有自行车。有 $n$ 个城市可供他们旅行。他们都住在城市 $1$，并想去位于城市 $n$ 的派对。城市地图可以看作是一个具有 $n$ 个节点和 $m$ 条边的无向图。第 $i$ 条边连接城市 $u_i$ 和 $v_i$，长度为 $w_i$。

光头强没有自行车，但他有钱。每个城市都有一辆自行车出售。第 $i$ 个城市的自行车具有慢速因子 $s_i$。一旦光头强购买了一辆自行车，他可以随时使用它从当前所在城市到任何相邻城市旅行，花费 $w_i×s_j$ 的时间，考虑他是通过拥有的自行车 $j$ 穿越边 $i$。

光头强可以购买任意数量的自行车，因为对他来说钱不是问题。由于光头强讨厌骑自行车，他希望以最短的时间从他的位置到达派对。由于他的计算机技能相当生疏，他向你寻求帮助。

从城市 $1$ 到城市 $n$，光头强需要的最短时间是多少？光头强不能没有自行车而旅行。保证光头强可以从城市 $1$ 到达任何其他城市。

输入格式

第一行包含一个整数 $t(1≤t≤100)$ — 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个以空格分隔的整数 $n$ 和 $m(2≤n≤1000；n−1≤m≤1000)$ — 城市数和道路数。

接下来的 $m$ 行中，每行包含三个整数 $u_i,v_i,w_i(1≤u_i,v_i≤n，u_i≠v_i；1≤w_i≤10^5)$，表示城市 $u_i$ 和 $v_i$ 之间存在长度为 $w_i$ 的道路。同一对城市可以由多条道路连接。

接下来一行包含 $n$ 个整数 $s_1,…,s_n(1≤s_i≤1000)$ — 每辆自行车的慢速因子。

所有测试用例中 $n$ 的总和不超过 $1000$，所有测试用例中 $m$ 的总和不超过 $1000$。

输入的额外约束条件：从城市 $1$ 到任何其他城市都是可行的。

输出格式

对于每个测试用例，输出一个整数，表示光头强从城市 $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

样例说明