Slavic 的所有朋友都计划从他们居住的地方骑自行车去参加聚会。除了斯拉夫之外,他们都有自行车。他们可以穿越 $$$n$$$ 的城市。他们都住在城市 $$$1$$$ 并想去参加位于城市 $$$n$$$ 的聚会。城市地图可以看作是具有 $$$n$$$ 节点和 $$$m$$$ 边的无向图。边 $$$i$$$ 连接城市 $$$u_i$$$ 和 $$$v_i$$$,长度为 $$$w_i$$$。
斯拉夫没有自行车,但他有的是钱。每个城市都有一辆自行车待售。第 $$$i$$$ 个城市的自行车的缓慢系数为 $$$s_{i}$$$。一旦 Slavic 购买了一辆自行车,他就可以随时使用它从当前所在的城市前往任何邻近的城市,只需花费 $$$w_i \cdot s_j$$$ 时间,考虑到他正在使用他拥有的自行车 $$$j$$$ 穿越边缘 $$$i$$$。
Slavic 可以购买任意数量的自行车,因为钱对他来说不是问题。由于 Slavic 讨厌骑自行车旅行,因此他希望在尽可能短的时间内从住处到达聚会场所。而且,由于他的信息学技能相当生疏,他向你寻求帮助。
斯拉夫从城市 $$$1$$$ 到城市 $$$n$$$ 最短需要多少时间?斯拉夫人没有自行车就不能旅行。保证斯拉夫可以从 $$$1$$$ 城市前往任何其他城市。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个空格分隔的整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 1000$$$; $$$n - 1 \leq m \leq 1000$$$) - 分别是城市数量和道路数量。
以下 $$$m$$$ 行中的第 $$$i$$$ 行每行包含三个整数 $$$u_i$$$, $$$v_i$$$, $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$; $$$1 \leq w_i \leq 10^5$$$),表示城市 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条长度为 $$$w_i$$$ 的道路。同一对城市可以通过多条道路连接。
下一行包含 $$$n$$$ 整数 $$$s_1, \ldots, s_n$$$ ($$$1 \leq s_i \leq 1000$$$) — 每辆自行车的缓慢系数。
所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$,所有测试用例的 $$$m$$$ 总和不超过 $$$1000$$$。
对输入的附加约束:可以从城市 $$$1$$$ 前往任何其他城市。
输出
对于每个测试用例,输出一个整数,表示斯拉夫语从城市 $$$1$$$ 开始到达城市 $$$n$$$ 的最短时间。
示例
输入 #1
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
输出 #1
19 36 14