В стране Капипаленд, в которой живут Куро и Широ, есть \(n\) городов, пронумерованных от \(1\) до \(n\), и \(m\) двусторонних дорог их соединяющих, пронумерованных от \(1\) до \(m\), \(i\)-я дорога соединяет города \(u_i\) и \(v_i\). Путешествовать между городами достаточно непросто, поэтому крайне развита индустрия такси. Чтобы выжить конкуренцию с другим такси, каждая компания должна найти свой особый подход к клиентам.
Куро является владельцем одной такси-компании. Он хочет ввести новую ценовую политику в своей компании, согласно которой цена поездки зависит не от длины поездки, а от суммы цен дорог, по которым проедет такси. Цену каждой из \(m\) дорог назначает лично Куро.
В настоящий момент, цена \(i\)-й дороги равна \(w_i\) и соответственно цена поездки на такси по дорогам \(e_1, e_2, \ldots, e_k\) равна \(\sum_{i=1}^k w_{e_i}\).
Однако Куро сам по себе не очень решительный человек, так что он подготовил \(q\) планов по изменению цен дорог. Каждый из планов основан на изначальных ценах \(w_i\), за исключением одной дороги \(t_j\), цена которой меняется на \(x_j\). Обратите внимание, что все планы независимы друг от друга.
Широ является постоянным клиентом такси Куро, так как она использует такси между городами \(1\) и \(n\) каждый день. Так как она настолько регулярный клиент, Куро решил показать ей все \(q\) своих планов перед тем как их опубликовать. Широ интересуется, какую наименьшую цену ей придётся заплатить за поездку из города \(1\) в город \(n\) в каждом из планов Куро.
Выходные данные
Выведите \(q\) целых чисел — наименьшую цену поездки, которую Широ придётся заплатить, чтобы добраться из города \(1\) в город \(n\) в каждом из \(q\) планов.
Примечание
В первом примере, дорожная система Капипаленд выглядит следующим образом, где число на дороге обозначает её изначальную цену:
В первом плане цены выглядят следующим образом:
Наименьшая возможная цену поездки Широ в этом плане равна \(4\), для этого ей нужно поехать по пути \(1 \rightarrow 4\).
Во втором плане цены выглядят следующим образом:
Наименьшая возможная цену поездки Широ в этом плане равна \(2\), для этого ей нужно поехать по пути \(1 \rightarrow 3 \rightarrow 4\).
В третьем плане цены выглядят следующим образом:
Наименьшая возможная цену поездки Широ в этом плане равна \(5\), для этого ей нужно поехать по пути \(1 \rightarrow 2 \rightarrow 4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5 6
1 2 2
2 4 3
1 4 7
1 3 1
3 4 5
3 4
5 1
3 8
1 4
2 1
3 1
|
4
2
5
6
3
1
|
|
2
|
2 4 4
1 2 2
1 2 3
1 2 4
1 2 5
2 1
3 2
4 3
1 5
|
1
2
2
3
|
|
3
|
2 1 1
1 2 1
1 3
|
3
|