暂无测试数据。

萨摩耶拿了一堆木棒给 $DD$ ，每条木棒有起点终点 $u,v$ ，萨摩耶让 $DD$ 求出这些边的最小生成树， $DD$ 很快就完成了，萨摩耶不开心，就又让 $DD$ 求出从 $[L,R]$ 之间的边中选出边使图中联通块最少的情况下代价为多少。

给定一张图 $n$ 个点 ，$m$ 条边，每条边有 $u,v,w$ 三个属性，$u,v$ 表示边连接的两个点，$w$ 表示这条边的代价，给定 $[L,R]$ 这个区间，从中选择边连起来使图中联通块最少(不保证一定会形成整张图的生成树)，在这种情况下的最小代价是多少

输入格式

第一行三个整数 $n,m,q$

接下来 $m$ 行，每行 $3$ 个整数，表示 $u_i,v_i,w_i$

再接下来 $q$ 行 ，每行 $2$ 个整数，表示 $L_i,R_i$

输出格式

对于每次询问输出最小代价

数据范围

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

对于另外 $20\%$ 的数据， $w_i$ 与 $i$ 成比例关系($w_i /i \leq 1$)

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

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

3 5 2
1 3 2
2 3 1
2 1 6
3 1 7
2 3 7
1 3 100
2 5
3 4

7
13