题目背景

用虚构的意义 就此把我给代替

把那些烧掉的诗句 再塞入我梦境

——MOCKER44.《虚构义》

题目描述

“广厦亭亭　驰道交通　八方施力　大业既成”

虚构世界同样有道路，具体地，这片区域有 $h$ 个点，其间有 $n$ 种可以修建的双向道路，每种道路有修建代价 $w_i$。然而虚构世界不够稳定，有时只有部分道路可供修建。

因此需回答 $q$ 个询问，每次只能修建编号在 $[l,r]$ 内的道路，求使全部 $h$ 个点两两可达需花费的最小代价，若无法满足要求则输出 $-1$。

输入格式

第一行三个整数 $h,n,q$，分别表示地点数、道路数和询问数。

之后 $n$ 行每行三个整数 $u_i,v_i,w_i$，表示该种道路连接 $u_i,v_i$ 两个地点，代价为 $w_i$。

之后 $q$ 行每行两个整数 $[l,r]$，表示该次询问的区间。

输出格式

$q$ 行，每行一个整数，表示该次询问的答案。

输入输出样例 #1

输入 #1

2 5 3
1 2 2
2 1 10
2 1 16
1 2 12
1 2 8
2 4
2 5
1 3

输出 #1

10
8
2

输入输出样例 #2

输入 #2

3 8 7
3 1 98
3 2 40
3 2 59
3 2 69
2 3 25
3 1 61
1 2 9
2 1 3
5 7
5 8
7 7
6 7
3 5
4 8
4 5

输出 #2

34
28
-1
70
-1
28
-1

说明/提示

对于所有数据，$1\le n,q\le 5\times 10^5,1\le w_i\le 10^9,1\le u_i,v_i\le h\le 10,u_i\ne v_i$。 \begin{array}{|c|c|c|} \hline \textbf{测试点编号} & n,q\le & \textbf{特殊性质}\\ \hline 1,2,3 & 1000 & \textbf{无}\\ \hline 4,5,6 & 7000 & \textbf{无}\\ \hline 7,8 & 5\times 10^5 & h=2\\ \hline 9,10 & 10^5 & w_i\le 3\\ \hline 11,12,13 & 10^5 & \textbf{无}\\ \hline 14,15,16,17 & 3\times 10^5 & \textbf{无}\\ \hline 18,19,20 & 5\times 10^5 & \textbf{无}\\ \hline \end{array}