题目描述

wwx 的公司接到了一个造路的需求，甲方表示她们公司一共有 $n$ 栋楼，她们希望花最少的钱使得这 $n$ 栋楼之间可以互相到达，建设规划的任务被派给了 wwx

认真的 wwx 立刻做了实地调研，给出了 $m$ 条可以修建道路的方案，每条方案表示第 $x$ 栋楼和第 $y$ 栋楼之间可以修建一条道路，花费为 $v$

但是甲方的领导是新官上任，所谓新官上任三把火，什么事不管懂不懂她都要插一手

于是她大手一挥，在 wwx 给出的方案书上画了个圈，把第 $l$ 条到第 $r$ 条方案圈了起来（包括 $l,r$)，规定 wwx 只能建这些被她圈起来的道路

虽然被一个外行指手画脚瞎搞很不开心，但是毕竟她们是甲方，无奈的 wwx 秉承着善良的原则，还是决定完成任务

所以 wwx 想知道，现在使得所有楼可以互相到达的最小花费是多少？

如果无法使得所有的楼都互相到达，那就使尽可能多的楼可以互相到达

输入格式

第一行三个整数 $n,m,q$，表示有 $n$ 栋楼，$m$ 条修路方案和 $q$ 次询问

接下来 $m$ 行，每行 $3$ 个整数 $x_i,y_i,v_i$ 表示第 $i$ 条修路方案是在 $x_i，y_i$ 之间建一条路，花费为 $v_i$

再接下来 $q$ 行 ，每行 $2$ 个整数 $l,r$，表示只允许使用 $[l,r]$ 这个区间编号的修路方案

输出格式

对于每次询问，输出使尽可能多的楼可以互相到达的最少的花费

数据范围

对于 $30\%$ 的数据， $m,q \leq 1000$

对于另外 $20\%$ 的数据， $v_i$ 与 $i$ 成比例关系

对于 $90\%$ 的数据，$n \leq 100, m \leq 10^4, q \leq 10^4, v_i \leq 10^6$

对于 $100\%$ 的数据，$n \leq 100, m \leq 2*10^4, q \leq 2*10^4, v_i \leq 10^6$

对于所有数据保证 $1 \leq x_i,y_i \leq n$

样例输入

4 8 3
1 3 2
4 2 1
2 3 1
1 4 3
2 1 6
3 1 8
2 4 3
2 3 7
3 6
1 2
5 8

样例输出

10
3
16

样例解释

对于第一次询问可以使得 $4$ 栋楼全部连通，选择 $(2,3),(1,4),(2,1)$ 三条边，花费为 $1+3+6=10$

对于第二次询问最多只能使得 $1,3$ 连通和 $2,4$ 连通，最小花费为 $2+1=3$

对于第三次询问可以使得 $4$ 栋楼全部连通，选择 $(2,1),(2,4),(2,3)$ 三条边，花费为 $6+3+7=16$