题目描述

给定 $n$ 个点及 $m$ 条边，每条边都是双向的，第 $i$ 条边的权重为 $c_i$。请处理 $q$ 个询问，每个询问有两个参数 $l$ 和 $r$，输出仅使用编号在 $l$ 和 $r$ 之间的边可以构成的最小生成树的权重之和，如果不存在，输出 -1。

输入格式

第一行：三个正整数表示 $n$，$m$ 和 $q$。 接下来 $m$ 行：每行三个整数表示 $a_i$，$b_i$ 和 $c_i$，代表一条边连接 $a_i$ 号点和 $b_i$ 号点，$a_i\neq b_i$，其权重为 $c_i$。 接下来 $q$ 行：每行两个整数表示 $l_i$ 和 $r_i$，代表一条查询的两个参数。

输出格式

对于每一条查询，输出一个整数，若编号在参数范围内的边可以构成生成树，则输出其中最小生成树的权重之和；否则输出 -1。

3 4 2
1 2 20 
2 3 30
1 3 40
1 3 10
1 3
3 4

50
-1

数据范围

• $1\leq n\leq 100$；
• $1\leq c_i\leq 50000$；
• 对于 $30\%$ 的数据，$m\leq 1000$，$q\leq 1000$
• 对于 $60\%$ 的数据，$m\leq 10000$，$q\leq 10000$
• 对于 $100\%$ 的数据，$1\leq m\leq 40000$，$1\leq q\leq 40000$。