F. Цена поездки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В стране Капипаленд, в которой живут Куро и Широ, есть $$$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$$$ в каждом из планов Куро.

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

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m, q \le 2 \cdot 10^5$$$) — количество городов, количество дорог и количество планов, которые набросал Куро.

$$$i$$$-я из следующих $$$m$$$ строк содержит три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w_i \le 10^9$$$, $$$u_i \ne v_i$$$) — концы и исходная цена $$$i$$$-й дороги.

Гарантируется, что существует хотя бы один способ добраться из города $$$1$$$ в город $$$n$$$ по данным $$$m$$$ двусторонним дорогам.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$t_j$$$ и $$$x_j$$$ ($$$1 \leq t_j \leq m, 1 \leq x_j \leq 10^9$$$) — номер дороги меняющейся в очередном плане и её новая цена.

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

Выведите $$$q$$$ целых чисел — наименьшую цену поездки, которую Широ придётся заплатить, чтобы добраться из города $$$1$$$ в город $$$n$$$ в каждом из $$$q$$$ планов.

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

В первом примере, дорожная система Капипаленд выглядит следующим образом, где число на дороге обозначает её изначальную цену:

В первом плане цены выглядят следующим образом:

Наименьшая возможная цену поездки Широ в этом плане равна $$$4$$$, для этого ей нужно поехать по пути $$$1 \rightarrow 4$$$.

Во втором плане цены выглядят следующим образом:

Наименьшая возможная цену поездки Широ в этом плане равна $$$2$$$, для этого ей нужно поехать по пути $$$1 \rightarrow 3 \rightarrow 4$$$.

В третьем плане цены выглядят следующим образом:

Наименьшая возможная цену поездки Широ в этом плане равна $$$5$$$, для этого ей нужно поехать по пути $$$1 \rightarrow 2 \rightarrow 4$$$.