Problem4639--搭积木

4639: 搭积木

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

萨摩耶拿了一堆木棒给 DDDDDD ,每条木棒有起点终点 u,vu,vu,v ,萨摩耶让 DDDDDD 求出这些边的最小生成树, DDDDDD 很快就完成了,萨摩耶不开心,就又让 DDDDDD 求出从 [L,R][L,R][L,R] 之间的边中选出边使图中联通块最少的情况下代价为多少。
给定一张图 nnn 个点 ,mmm 条边,每条边有 u,v,wu,v,wu,v,w 三个属性,u,vu,vu,v 表示边连接的两个点,www 表示这条边的代价,给定 [L,R][L,R][L,R] 这个区间,从中选择边连起来使图中联通块最少(不保证一定会形成整张图的生成树),在这种情况下的最小代价是多少。

Input

第一行三个整数 n,m,qn,m,qn,m,q。
接下来 mmm 行,每行 333 个整数,表示 ui,vi,wiu_i,v_i,w_iui,vi,wi。
再接下来 qqq 行 ,每行 222 个整数,表示 Li,RiL_i,R_iLi,Ri。

Output

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

Sample 1 Input

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

Sample 1 Output

7
13

HINT

【数据范围】
对于 30%30\%30% 的数据, m,q≤1000m,q \leq 1000m,q1000。
对于另外 20%20\%20% 的数据, wiw_iwiiii 成比例关系(wi/i≤1w_i /i \leq 1wi/i1)。
对于 90%90\%90% 的数据,n≤100,m≤104,q≤104,wi≤106n \leq 100, m \leq 10^4, q \leq 10^4, w_i \leq 10^6n100,m104,q104,wi106
对于 100%100\%100% 的数据,n≤100,m≤2∗104,q≤2∗104,wi≤106n \leq 100, m \leq 2*10^4, q \leq 2*10^4, w_i \leq 10^6n100,m2104,q2104,wi106
【样例解释】
对于第一次询问,可以把原图变为最少 111 个联通块,最小代价是 1+61+61+6。
对于第二次询问,可以把原图变为最少 111 个联通块,最小代价是 6+76+76+7。

Source/Category