题目描述

Anna 负责为北海新建的一个海上风电场设计电缆布线。该风电场有 $N$ 台风力发电机，编号为 $0, 1, \ldots, N-1$。她的目标是确保所有发电机都能以最低的成本与陆地（岸边）连通。

Anna 拥有 $M$ 条可选的连接，每条连接都连接两台风力发电机，并有一个特定的费用。此外，附近的城市同意承担将一段连续编号区间 $[\ell, r]$ 内的发电机直接接入岸边的费用。也就是说，区间内的每台发电机 $t$（$\ell \leq t \leq r$）都可以免费直接接入岸边。如果所有可选连接都建成，则任意两台发电机之间都可以互相到达。这意味着只要有一台发电机接入岸边，就可以通过某些连接让所有发电机的电力都输送到岸边。当然，如果有更多发电机直接接入岸边，可能可以进一步降低总成本。注意，免费连接是唯一能直接连到岸边的方式。

Anna 的任务是选择一部分可选连接，使得它们的总费用最小，并保证每台发电机都能通过某些路径与岸边连通（可以经过其他发电机）。

为了让 Anna 做出明智的决策，城市方提供了 $Q$ 种不同的区间 $[\ell, r]$ 方案。城市方希望 Anna 计算在每种方案下的最小总费用。

输入格式

第一行包含三个整数 $N$、$M$ 和 $Q$。

接下来的 $M$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $c_i$，表示一条可选的无向连接，连接发电机 $u_i$ 和 $v_i$，费用为 $c_i$。每对发电机之间至多有一条直接连接，且 $u_i \neq v_i$。保证如果所有可选连接都建成，任意两台发电机之间都可以互相到达。

接下来 $Q$ 行，每行两个整数 $\ell_i$ 和 $r_i$，表示一种方案，在该方案下，岸边直接接入区间 $[\ell_i, r_i]$ 内的所有发电机。注意，可能有 $r_i = \ell_i$，即岸边只直接接入一台发电机。

输出格式

输出 $Q$ 行，每行一个整数，表示在对应方案下，使所有发电机都能把电送到岸边所需的最小总费用。

输入输出样例 #1

输入 #1

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

输出 #1

14
8
2

输入输出样例 #2

输入 #2

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

输出 #2

0
6
4
11

输入输出样例 #3

输入 #3

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

输出 #3

12
10
10
10

输入输出样例 #4

输入 #4

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

输出 #4

5
4
6

输入输出样例 #5

输入 #5

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

输出 #5

7
0
12
6

输入输出样例 #6

输入 #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

输出 #6

1
14
22
24

输入输出样例 #7

输入 #7

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

输出 #7

5000000000

说明/提示

样例说明

在第一个样例中，给定如下图的可选连接：

有三种方案。第一种方案中，只有发电机 $1$ 直接接入岸边，此时需要保留除 $(0,2)$ 以外的所有连接，总费用为 $2 + 3 + 6 + 3 = 14$。第二种方案中，发电机 $3$ 和 $4$ 直接接入岸边，此时只需保留 $(1,0)$、$(1,2)$ 和 $(2,4)$，总费用为 $8$。第三种方案中，除了发电机 $0$ 以外，其他都直接接入岸边，此时只需将 $0$ 与任一发电机连接即可，选择 $(0,1)$，费用为 $2$。下图展示了三种方案的最优方案：

第一个和第六个样例满足测试组 $2$、$5$、$7$ 的约束。第二个和第七个样例满足测试组 $1$、$2$、$5$、$7$ 的约束。第三个样例满足测试组 $2$、$3$、$5$、$7$ 的约束。第四个样例满足测试组 $2$、$4$、$5$、$7$ 的约束。第五个样例满足测试组 $2$、$5$、$6$、$7$ 的约束。

约束与评分

• $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$，且每对发电机之间至多有一条直接连接
• $1 \leq c_i \leq 1000000000$
• $0 \leq \ell_i \leq r_i \leq N-1$

你的解答将在一组测试组上进行评测，每组有若干测试用例。要获得该测试组的分数，你需要通过该测试组的所有测试用例。

组别	分值	限制条件
1	8	$M = N - 1$，且第 $i$ 条连接为 $u_i = i$，$v_i = i + 1$，即所有连接连成一条链 $0 \leftrightarrow 1 \leftrightarrow 2 \leftrightarrow \ldots \leftrightarrow N - 1$
2	11	$N, M, Q \leq 2000$ 且 $\sum (r_i - \ell_i + 1) \leq 2000$
3	13	对所有 $i$，$r_i = \ell_i + 1$
4	17	对所有 $i$，$1 \leq c_i \leq 2$，即每条连接的费用为 $1$ 或 $2$
5	16	$\sum (r_i - \ell_i + 1) \leq 400000$
6	14	对所有 $i$，$\ell_i = 0$
7	21	无额外限制