310973: CF1915G. Bicycles

G. Bicyclestime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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

ExampleInput

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

Output

19
36
14

题目大意：
斯拉夫和他的朋友们住在城市1，他们计划骑自行车去城市n参加派对。有n个城市和m条道路，道路可以双向通行。每条道路i连接城市u_i和v_i，长度为w_i。每个城市都有一辆自行车出售，第i个城市的自行车慢速因子为s_i。斯拉夫可以购买任意数量的自行车，他想以最短的时间从城市1到达城市n。求斯拉夫从城市1到城市n所需的最短时间。

输入数据格式：
第一行包含一个整数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到城市n所需的最短时间。题目大意： 斯拉夫和他的朋友们住在城市1，他们计划骑自行车去城市n参加派对。有n个城市和m条道路，道路可以双向通行。每条道路i连接城市u_i和v_i，长度为w_i。每个城市都有一辆自行车出售，第i个城市的自行车慢速因子为s_i。斯拉夫可以购买任意数量的自行车，他想以最短的时间从城市1到达城市n。求斯拉夫从城市1到城市n所需的最短时间。 输入数据格式： 第一行包含一个整数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到城市n所需的最短时间。