ioi-2050-2

This is year 2050 and your school is hosting IOI 2050 this time. To organize the contest a lot of LAN cables will be laid down. N students from different countries will be coming to earn the prize of IOI winner. You are being asked to come up with a plan such that LAN utilization is minimized and all computers are connected to each other diretly or undirectly. LAN will be laid to connect these N computers. You will be given information about which computer to be connected to which and distance between them.
After you have come up with a plan you will be asked M queries of the form u,v for which you have to tell the minimum length of LAN used connect computers u and v according to your plan.

[Input]
First line contains a single integer t, denoting number of test cases.
Each test case begins with a line containing 3 integers N,P,M denoting number of students, number of connections and number of queries respectively.
Next p line contains 3 integers u,v,d each denoting computer u and computer v and d denoting distance between them.
Next M line contains 2 integers u,v each denoting computer u and v.

[Output]
For each test case print "Case: case_no" followed by m queries solution.
For each query output the minimum length of cable used to connect u and v.

[Constraints]
1 ≤ t ≤ 50 
1 ≤ N ≤ 1000 
N-1 ≤ P ≤ 100000
1 ≤ M ≤ 100000
1 ≤ u,v ≤ N
1 ≤ d ≤ 1000000
Within each test case d for each connection will be unique.
NOTE: Use scanf/printf. Large Input data.

SAMPLE INPUT
1
6 9 5
1 2 5
1 3 4
1 4 6
2 3 2
3 4 1
2 5 9
3 5 3
4 6 7
5 6 10
1 2
2 3
3 4
4 5
5 6

SAMPLE OUTPUT
Case: 1
6
2
1
4
11

Source: hackerearth | Difficulty: MEDIUM
Tags: Spanning trees

Graph algorithms

Graph traversal


Solutions: