Indecisive Taxi Fee
Contest: Codeforces Round 558 (Div. 2)
Difficulty rating: 3000
Tags: data structures, graphs, shortest paths

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.

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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$$$.

Example input:
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

Example output:
4
2
5
6
3
1

Example input:
2 4 4
1 2 2
1 2 3
1 2 4
1 2 5
2 1
3 2
4 3
1 5

Example output:
1
2
2
3

Editorial:
Firstly, we will find and trace out one shortest path from vertex $$$1$$$ to vertex $$$n$$$ in the graph. Let's call this path main path, and we will number the edges on the main path as $$$E_1$$$, $$$E_2$$$, .., $$$E_k$$$ respectively. We will also call all of the other edges that does not belong to this main path candidate edges.
During the procedure, we can also calculate the shortest path from $$$1$$$ to every vertex $$$u$$$, and the shortest path from every vertex $$$u$$$ to $$$n$$$. After calculating all of these values, we can now query the shortest path from $$$1$$$ to $$$n$$$ that must pass through each edge $$$(u, v)$$$ in either direction.
We have a few observations to be made here:
Observation 1: Apart of the vertices belong to the main path, for each vertex $$$u$$$, the shortest path from $$$1$$$ to $$$u$$$ uses a prefix of the main path. More formally, there exists an index $$$l_u$$$ ($$$0 \leq l_u \leq k$$$) such that the shortest path from $$$1$$$ to $$$u$$$ must use the edges $$$E_1$$$, $$$E_2$$$, ..., $$$E_{l_u}$$$ at its beginning.
Using the same analogy, we can say that for each vertex $$$u$$$, the shortest path from $$$u$$$ to $$$n$$$ uses a suffix of the main path; or in other words, there exists an index $$$r_u$$$ ($$$1 \leq r_u \leq k + 1$$$) such that the shortest path from $$$u$$$ to $$$n$$$ must use the edges $$$E_{r_u}$$$, $$$E_{r_{u + 1}}$$$, ..., $$$E_k$$$ at its end. Note that if $$$l_u = 0$$$, the shortest path from $$$1$$$ to $$$u$$$ does not use a prefix of the main path, and if $$$r_u = k + 1$$$, the shortest path from $$$u$$$ to $$$n$$$ does not use a suffix of the main path.
For every vertex $$$v$$$ that belongs to the main path however, we will set $$$l_v = t, r_v = t + 1$$$, where $$$t$$$ is the position where $$$v$$$ appears on the main path.
What does this imply? This implies that the shortest from $$$1$$$ to $$$n$$$ that passes through $$$u$$$ does not rely on the edges $$$E_{l_u + 1}$$$, $$$E_{l_u + 2}$$$, ..., $$$E_{r_u - 1}$$$.
Observation 2: For each candidate edge $$$(u, v)$$$, the shortest path from $$$1$$$ to $$$n$$$ passing through this edge in the order $$$u \rightarrow v$$$ does not rely on the edges $$$E_{l_u + 1}$$$, $$$E_{l_u + 2}$$$, ..., $$$E_{r_v - 1}$$$. This is because, the shortest path passing through this order $$$u \rightarrow v$$$ will consist of the shortest path from $$$1$$$ to $$$u$$$, the edge $$$(u, v)$$$, and the shortest path from $$$v$$$ to $$$n$$$. With the same analogy, the shortest path from $$$1$$$ to $$$n$$$ passing through this edge in the order $$$v \rightarrow u$$$ does not rely on the edges $$$E_{l_v + 1}$$$, $$$E_{l_v + 2}$$$, ..., $$$E_{r_u - 1}$$$.
Using the observations, we can now answer the queries.
There are three cases that we should consider when answering the shortest path with the modified edge:
• The modified edge is a candidate edge (i.e. it does not belong to the main path): we will take the minimal of the main path and the shortest path that goes through this modified edge.
• The modified edge belongs to the main path, and its value decreases: the new shortest path is still the main path, and its new value is the old value subtracting the difference between the original and the modified weight of that edge.
• The modified edge belongs to the main path, and its value increases: the new shortest path is either one of these two options:   The main path, its new value being the old value adding the weight-difference of the modified edge.  The shortest path from $$$1$$$ to $$$n$$$ that does not use the modified edge. This shortest path must use a candidate edge, since we cannot reuse the main path anymore; more specifically, this shortest path uses a candidate edge that does not rely on the modified edge. To get the value of this option, recall in observation 2 that for each candidate edge $$$(u, v)$$$ and with its direction, we know the range of edges belonging to the main path that this candidate edge does not rely on. Hence, we can use a segment tree to manage and query the shortest path that does not rely on this edge.
• The main path, its new value being the old value adding the weight-difference of the modified edge.
• The shortest path from $$$1$$$ to $$$n$$$ that does not use the modified edge. This shortest path must use a candidate edge, since we cannot reuse the main path anymore; more specifically, this shortest path uses a candidate edge that does not rely on the modified edge. To get the value of this option, recall in observation 2 that for each candidate edge $$$(u, v)$$$ and with its direction, we know the range of edges belonging to the main path that this candidate edge does not rely on. Hence, we can use a segment tree to manage and query the shortest path that does not rely on this edge.
Complexity: $$$O((m + n)\log{n})$$$.