题目描述

Anna has been tasked with designing the wiring for a new offshore wind farm in the North Sea consisting of $N$ turbines, numbered $0, 1, \ldots, N-1$. Her goal is to ensure that all turbines are connected to the shore as cheaply as possible.

Anna has a list of $M$ potential connections, each linking two wind turbines and having a specific cost. Additionally, the nearby city has agreed to cover the costs of connecting a consecutive interval $[\ell, r]$ of turbines to the shore. That is, each turbine $t$ in this range ($\ell \leq t \leq r$) is directly connected to the shore for free. If all potential connections are built, there is a way to reach any wind turbine from any other wind turbine. That implies that as soon as one of the wind turbines is connected to the shore, it is possible to build connections such that the power from all the turbines can be transferred to the shore. Of course, more connections to the shore may allow for a cheaper total cost. Note that the free connections are the only direct ones to the shore.

It is Anna's job to select a subset of the potential connections in a way that minimizes the sum of their costs, while ensuring that every wind turbine can reach the shore (possibly via other wind turbines).

In order to make an informed decision, the city provides Anna with $Q$ possible options for the interval $[\ell, r]$. The city asks Anna to compute the minimum cost for each of these scenarios.

输入格式

The first line of the input contains three integers, $N$, $M$ and $Q$.

The following $M$ lines contain three integers each, $u_i$, $v_i$ and $c_i$. The $i$th line describes a potential connection between wind turbines $u_i$ and $v_i$ that has the cost $c_i$. These connections are undirected and connect two different turbines. No two connections are between the same pair of turbines. It is guaranteed that, if all potential connections are built, any wind turbine is reachable from any other (directly or indirectly).

The next $Q$ lines contain two integers each, $\ell_i$ and $r_i$, describing the scenario where the shore directly connects to the wind turbines $\ell_i, \ell_i + 1, \ldots, r_i$. Note that we can have $r_i = \ell_i$ when the shore directly connects to a single wind turbine.

输出格式

Output $Q$ lines, one line per scenario, containing one integer each, the minimum cost of connecting the turbines such that every turbine can deliver its power to the shore.

5 5 3
1 0 2
0 2 5
1 2 3
3 0 6
2 4 3
1 1
3 4
1 4

14
8
2

5 4 4
0 1 3
1 2 1
2 3 5
3 4 2
0 4
2 3
2 4
2 2

0
6
4
11

7 7 4
6 4 3
1 4 5
3 2 4
0 3 2
5 2 3
4 0 1
1 3 1
0 1
2 3
4 5
5 6

12
10
10
10

7 7 3
2 6 1
1 0 1
0 5 1
1 2 2
3 4 1
5 3 1
5 4 1
5 6
1 3
3 4

5
4
6

7 7 4
6 4 3
1 4 5
3 2 4
0 3 2
5 2 3
4 0 1
1 3 1
0 3
0 6
0 1
0 4

7
0
12
6

9 13 4
0 1 1
2 0 3
1 2 4
5 4 4
2 5 6
3 1 7
8 1 4
6 3 9
0 3 5
3 5 3
4 3 2
6 2 4
7 8 5
1 8
4 7
6 7
1 2

1
14
22
24

6 5 1
0 1 1000000000
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
1 1

5000000000

提示

Examples

In the first example, we are given the following graph of potential connections.

We are given three scenarios. In the first scenario, turbine $1$ is the only one with a connection to the shore. In this case, we need to keep all connections except for the connection between turbine $0$ and turbine $2$, giving a total cost of $2 + 3 + 6 + 3 = 14$. In the next scenario, the turbines $3$ and $4$ are connected to the shore. In this case, we keep the connections $(1,0)$, $(1,2)$ and $(2,4)$, giving a cost of $8$. In the third scenario, all but turbine $0$ are connected to the shore. In this case, we only need to connect this one to another turbine, which we do by choosing the connection $(0,1)$. The solutions to the scenarios are depicted below:

The first and the sixth samples satisfy the constraints of test groups $2$, $5$ and $7$. The second and the seventh samples satisfy the constraints of test groups $1$, $2$, $5$ and $7$. The third sample satisfies the constraints of test groups $2$, $3$, $5$ and $7$. The fourth sample satisfies the constraints of test groups $2$, $4$, $5$ and $7$. The fifth sample satisfies the constraints of test groups $2$, $5$, $6$ and $7$.

Constraints and Scoring

• $2 \leq N \leq 100000$.
• $1 \leq M \leq 100000$.
• $1 \leq Q \leq 200000$.
• $0 \leq u_i, v_i \leq N-1$.
• $u_i \neq v_i$, and there is at most one direct connection between each pair of wind turbines.
• $1 \leq c_i \leq 1000000000$.
• $0 \leq \ell_i \leq r_i \leq N-1$.

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group, you need to solve all the test cases in the test group.

Group	Score	Limits
1	8	$M = N - 1$ and the $i$th connection has $u_i = i$ and $v_i = i + 1$, i.e. if all connections are built, they form a path $0 \leftrightarrow 1 \leftrightarrow 2 \leftrightarrow \ldots \leftrightarrow N - 1$
2	11	$N, M, Q \leq 2000$ and $\sum (r_i - \ell_i + 1) \leq 2000$
3	13	$r_i = \ell_i + 1$ for all $i$
4	17	$1 \leq c_i \leq 2$ for all $i$, i.e., each connection has cost either $1$ or $2$
5	16	$\sum (r_i - \ell_i + 1) \leq 400000$
6	14	$\ell_i = 0$ for all $i$
7	21	No additional constraints