在Kuro和Shiro居住的Capypaland市,有$$$n$$$个城镇,编号从$$$1$$$到$$$n$$$,有$$$m$$$双向道路连接它们,编号从$$$1$$$到$$$m$$$。第 $$$i$$$ 条道路连接城镇 $$$u_i$$$ 和 $$$v_i$$$。由于城镇之间的交通相当困难,因此出租车行业在这里非常受欢迎。为了在激烈的竞争中生存,每个出租车公司都必须为他们的客户找到独特的特征。
Kuro 是一家出租车公司的老板。他决定为他的出租车品牌引入一种新的收费模式,每次乘车的费用不是根据行程长度计算,而是根据所行驶道路的价格总和计算。每条 $$$m$$$ 道路的价格均由 Kuro 亲自决定。
截至目前,道路 $$$i$$$ 的价格为 $$$w_i$$$,因此出租车经过道路 $$$e_1、e_2、\ldots、e_k$$$ 的费用为 $$$\sum_{i=1}^k w_{e_i}$$$。
然而,Kuro本人是一个优柔寡断的人,所以他起草了$$$q$$$计划来改变道路价格。各方案均以原价格$$$w_i$$$为基础,但单条道路$$$t_j$$$的价格改为$$$x_j$$$。请注意,这些计划是相互独立的。
Shiro 是 Kuro 出租车品牌的常客,因为她每天使用出租车从镇 $$$1$$$ 到镇 $$$n$$$。由于她是一位常客,Kuro 决定在向公众发布之前向她展示他所有的 $$$q$$$ 计划。现在,Shiro 想知道对于每个 Kuro 的计划,从 $$$1$$$ 镇到 $$$n$$$ 镇所需支付的最低费用。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m, q \le 2 \cdot 10^5$$$)——分别是 Kuro 起草的城镇数量、道路数量和计划数量。
下一个 $$$m$$$ 的第 $$$i$$$ 包含三个整数 $$$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$$$ 条道路的原始价格。
保证至少有一种方式可以使用这些 $$$m$$$ 双向道路从城镇 $$$1$$$ 前往城镇 $$$n$$$。
接下来的 $$$q$$$ 行包含两个整数 $$$t_j$$$ 和 $$$x_j$$$ ($$$1 \leq t_j \leq m, 1 \leq x_j \leq 10^9$$$) - Kuro 计划更改的道路索引及其新价格。
输出
打印 $$$q$$$ 整数 - Shiro 在每个 $$$q$$$ 计划中从城镇 $$$1$$$ 到城镇 $$$n$$$ 必须支付的最低费用。
示例
输入 #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
输出 #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
输出 #2
1 2 2 3
输入 #3
2 1 1 1 2 1 1 3
输出 #3
3
注意
在第一个示例中,Capypaland 的原始概述如下所示,其中每条道路旁边的数字表示道路的原始价格,
第一个计划的概述,
Shiro在此计划中必须支付的最低费用是$$$4$$$,对应路径$$$1 \rightarrow 4$$$。
第二个计划的概述,
Shiro在此计划中必须支付的最低费用是$$$2$$$,对应路径$$$1 \rightarrow 3 \rightarrow 4$$$。
第三个计划概述,
Shiro在此计划中必须支付的最低费用是$$$5$$$,对应路径$$$1 \rightarrow 2 \rightarrow 4$$$。