CF1915G.Bicycles

All of Slavic's friends are planning to travel from the place where they live to a party using their bikes. And they all have a bike except Slavic. There are $n$ cities through which they can travel. They all live in the city $1$ and want to go to the party located in the city $n$. The map of cities can be seen as an undirected graph with $n$ nodes and $m$ edges. Edge $i$ connects cities $u_i$ and $v_i$ and has a length of $w_i$.

Slavic doesn't have a bike, but what he has is money. Every city has exactly one bike for sale. The bike in the $i$-th city has a slowness factor of $s_{i}$. Once Slavic buys a bike, he can use it whenever to travel from the city he is currently in to any neighboring city, by taking $w_i \cdot s_j$ time, considering he is traversing edge $i$ using a bike $j$ he owns.

Slavic can buy as many bikes as he wants as money isn't a problem for him. Since Slavic hates traveling by bike, he wants to get from his place to the party in the shortest amount of time possible. And, since his informatics skills are quite rusty, he asks you for help.

What's the shortest amount of time required for Slavic to travel from city $1$ to city $n$? Slavic can't travel without a bike. It is guaranteed that it is possible for Slavic to travel from city $1$ to any other city.

斯拉维克的所有朋友都计划骑自行车从他们居住的地方前往一场聚会。但斯拉维克自己没有自行车。一共有 $n$ 座城市可供通行。他们全都住在第 $1$ 号城市，而聚会则在第 $n$ 号城市举行。城市地图可视为一个包含 $n$ 个节点和 $m$ 条边的无向图。第 $i$ 条边连接城市 $u_i$ 和 $v_i$，其长度为 $w_i$。

斯拉维克没有自行车，但他有钱。每座城市恰好出售一辆自行车。第 $i$ 号城市的自行车具有“迟缓因子” $s_{i}$。一旦斯拉维克购买了一辆自行车，他便可随时使用它：当他身处某城市并想前往任意一个相邻城市时，若他正使用所购得的第 $j$ 辆自行车来穿越第 $i$ 条边，则所需时间为 $w_i \cdot s_j$。

斯拉维克可以购买任意数量的自行车（金钱对他而言不是问题）。由于斯拉维克非常讨厌骑自行车，他希望以最短的时间从住所抵达聚会地点。又因他的信息学技能已相当生疏，他请求你提供帮助。

斯拉维克从第 $1$ 号城市到达第 $n$ 号城市的最短耗时是多少？注意：斯拉维克不能在不使用自行车的情况下移动。题目保证斯拉维克能够从第 $1$ 号城市到达任意其他城市。

The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two space-separated integers $n$ and $m$ ($2 \leq n \leq 1000$; $n - 1 \leq m \leq 1000$) — the number of cities and the number of roads, respectively.

The $i$-th of the following $m$ lines each contain three integers $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$), denoting that there is a road between cities $u_i$ and $v_i$ of length $w_i$. The same pair of cities can be connected by more than one road.

The next line contains $n$ integers $s_1, \ldots, s_n$ ($1 \leq s_i \leq 1000$) — the slowness factor of each bike.

The sum of $n$ over all test cases does not exceed $1000$, and the sum of $m$ over all test cases does not exceed $1000$.

Additional constraint on the input: it is possible to travel from city $1$ to any other city.

第一行包含一个整数 $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$ 出发可以到达任意其他城市。

For each test case, output a single integer denoting the shortest amount of time Slavic can reach city $n$ starting from city $1$.

对于每个测试用例，输出一个整数，表示斯拉维奇从城市 $1$ 出发到达城市 $n$ 所需的最短时间。