CF1163F.Indecisive Taxi Fee

In the city of Capypaland where Kuro and Shiro resides, there are $n$ towns numbered from $1$ to $n$ and there are $m$ bidirectional roads numbered from $1$ to $m$ connecting them. The $i$-th road connects towns $u_i$ and $v_i$. Since traveling between the towns is quite difficult, the taxi industry is really popular here. To survive the harsh competition, each taxi company has to find a distinctive trait for their customers.

Kuro is the owner of a taxi company. He has decided to introduce a new fee model for his taxi brand, where the fee for each ride is not calculated based on the trip length, but on the sum of the prices of the roads traveled. The price for each of the $m$ roads has been decided by Kuro himself.

As of now, the price for the road $i$ is $w_i$ and hence the fee for a taxi ride traveling through roads $e_1, e_2, \ldots, e_k$ is $\sum_{i=1}^k w_{e_i}$.

However, Kuro himself is an indecisive person, so he has drafted $q$ plans to change the road price. Each of the plans will be based on the original prices $w_i$, except for a single road $t_j$, the price of which is changed to $x_j$. Note, that the plans are independent of each other.

Shiro is a regular customer of the Kuro's taxi brand since she uses the taxi to travel from town $1$ to town $n$ every day. Since she's so a regular customer, Kuro decided to show her all his $q$ plans before publishing them to the public. Now, Shiro wants to know the lowest fee she must pay to travel from the town $1$ to the town $n$ for each Kuro's plan.

在库洛和史洛居住的卡皮亚兰德城中，共有 $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$ 所需支付的最低费用是多少？

The first line contains three integers $n$, $m$ and $q$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m, q \le 2 \cdot 10^5$) — the number of towns, the number of roads, and the number of plans that Kuro has drafted respectively.

The $i$-th of the next $m$ contains three integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$, $u_i \ne v_i$) — two endpoints and the original price of the $i$-th road.

It is guaranteed, that there is at least one way to travel from town $1$ to town $n$ using these $m$ bidirectional roads.

Each of the next $q$ lines contains two integers $t_j$ and $x_j$ ($1 \leq t_j \leq m, 1 \leq x_j \leq 10^9$) — the index of the road Kuro has planned to change and its new price respectively.

第一行包含三个整数 $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 计划修改的道路编号及其新价格。

Print $q$ integers — the lowest fee Shiro must pay to get from town $1$ to town $n$ in each of those $q$ plans.

输出 $q$ 个整数——在上述 $q$ 种方案中，Shiro 从城镇 $1$ 到达城镇 $n$ 所需支付的最低费用。

In the first example, the original overview of Capypaland looks like this, where the number next to each road denotes the original prices of the roads,

The overview of the first plan,

The lowest fee Shiro must pay in this plan is $4$, which corresponds to the path $1 \rightarrow 4$.

The overview of the second plan,

The lowest fee Shiro must pay in this plan is $2$, which corresponds to the path $1 \rightarrow 3 \rightarrow 4$.

The overview of the third plan,

The lowest fee Shiro must pay in this plan is $5$, which corresponds to the path $1 \rightarrow 2 \rightarrow 4$.

在第一个例子中，卡皮兰德（Capypaland）的原始概览如下图所示，其中每条道路旁的数字表示该道路的原始价格：

第一种方案的概览：

在此方案中，志郎（Shiro）需支付的最低费用为 $4$，对应路径 $1 \rightarrow 4$。

第二种方案的概览：

在此方案中，志郎需支付的最低费用为 $2$，对应路径 $1 \rightarrow 3 \rightarrow 4$。

第三种方案的概览：

在此方案中，志郎需支付的最低费用为 $5$，对应路径 $1 \rightarrow 2 \rightarrow 4$。