G. Велосипеды
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Все друзья Славика планируют отправиться на вечеринку на своих велосипедах из места, где они живут. У всех есть велосипеды, кроме Славика. Есть $$$n$$$ городов, через которые они могут путешествовать. Все живут в городе $$$1$$$ и хотят пойти на вечеринку, которая находится в городе $$$n$$$. Карту городов можно рассматривать как ненаправленный граф с $$$n$$$ узлами и $$$m$$$ ребрами. Ребро $$$i$$$ соединяет города $$$u_i$$$ и $$$v_i$$$ и имеет длину $$$w_i$$$.

У Славика нет велосипеда, но у него есть деньги. В каждом городе есть ровно один велосипед, который можно купить. У велосипеда в $$$i$$$-м городе есть коэффициент медлительности $$$s_{i}$$$. Как только Славик купит велосипед, он может использовать его, чтобы путешествовать из города, в котором он находится, в любой город. Проезд по ребру $$$i$$$ с использованием велосипеда $$$j$$$ занимает время $$$w_i \cdot s_j$$$.

Славик может купить столько велосипедов, сколько захочет, так как деньги для него не проблема. Славик ненавидит путешествовать на велосипеде, поэтому он хочет добраться на вечеринку за минимальное время. И поскольку он уже подзабыл информатику, он просит вас ему помочь.

Какое минимальное количество времени потребуется Славику, чтобы добраться из города $$$1$$$ в город $$$n$$$? Славик не может путешествовать без велосипеда. Гарантируется, что возможно добраться от города $$$1$$$ до любого другого города.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следует описание самих наборов.

Первая строка каждого набора содержит два целых числа, разделенных пробелом: $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 1000$$$; $$$n - 1 \leq m \leq 1000$$$) — количество городов и количество дорог, соответственно.

$$$i$$$-я из следующих $$$m$$$ строк содержит три целых числа $$$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$$$.

Пример
Входные данные
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