Ян и Татьяна решили стать блогерами-путешественниками и публиковать ролики о поездках по городам своей страны.

В стране есть \(n\) городов, пронумерованных от \(1\) до \(n\). Город \(1\) — столица их страны. Города соединены \(m\) двусторонними дорогами, пронумерованными от \(1\) до \(m\), каждая из которых соединяет два различных города. При этом одну и ту же пару городов могут соединять несколько различных дорог. Из любого города по дорогам можно доехать до любого другого города страны.

Путешественники планируют отправиться из столицы в какой-то другой город, но пока не выбрали в какой. Маршрут путешествия в город \(k\) будет состоять из городов \(s_1, s_2, \ldots, s_q\) и дорог \(r_1, r_2, \ldots, r_{q - 1}\), таких что:

• \(s_1 = 1\), \(s_q = k\);
• дорога \(r_i\) соединяет города \(s_i\) и \(s_{i+1}\);
• ребята не проезжают по одной и той же дороге дважды, поэтому все \(r_i\) различны. Допускается проезжать несколько раз через один и тот же город, в том числе через город \(1\), где путешествие начинается, и город \(k\), в котором путешествие заканчивается.

Для каждой дороги Ян и Татьяна посчитали длительность ролика, который получится при съемке путешествия по этой дороге, длительность ролика для дороги с номером \(i\) равна \(t_i\).

В процессе путешествия каждый из ребят выберет одну из дорог маршрута и снимет ролик, посвящённый этой дороге. При этом Ян любит снимать короткие ролики, поэтому выберет на маршруте дорогу с наименьшим значением \(t_i\), а Татьяна предпочитает длинные ролики, поэтому выберет дорогу с наибольшим значением \(t_i\).

Суммарная длина двух роликов будет равна \(\min\limits_{1 \leq i \leq q - 1} t_{r_i} + \max\limits_{1 \leq i \leq q - 1} t_{r_i}\).

Ребята планируют выложить ролики на известную платформу, где большей популярностью пользуются короткие ролики, поэтому они хотят минимизировать суммарную длину двух роликов. Чтобы выбрать конечный город и маршрут для путешествия, блогеры хотят для каждого конечного города \(k\) подсчитать минимальную по всем возможным маршрутам из города \(1\) в город \(k\) суммарную длину двух роликов.