Все друзья Славика планируют отправиться на вечеринку на своих велосипедах из места, где они живут. У всех есть велосипеды, кроме Славика. Есть \(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\) до любого другого города.
Выходные данные
Для каждого набора входных данных выведите одно целое число, обозначающее минимальное количество времени, за которое Славик может добраться из города \(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
|
19
36
14
|