修路

Time Limit: 3000 ms

Memory Limit: 65535 ms

Description

1-n个村庄,它们需要建一些路使相互之间连通,已知它们之间已经有一些建得很好的路,希望剩下的要建的路长度之和,越短越好。

Input

第一行 n,m,k,n表示村庄数(2<=n<=10000),m表示已建好的道路数(m<=10000),k(k<=100000)表示可以修建的路。2到m+1行,有a,b,c(1<=a,b<=n)三个整数表示村庄a和b之间已经修好了长度为c(0<=c<=100)的路,余下的k行,有a,b,c(1<=a,b<=n)表示村庄a和b可以建一条长度为c(0<=c<=100)的路径,使两村庄连通。 (多组case 以n为0结尾,会有重边)

Output

如果不能连通输出-1;否则输出最小的修路总长度。

Sample Input

3 1 2
1 2 5
1 3 1
3 2 1
0

Sample Output

1 

Hint

Source

gaozhen

提交代码