Problem Description
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A graph is a collection of vertices and a collection of edges that connect pairs of vertices.
Simple word, we have an undirected graph with weight on its edge, and we want to choose a key point on this graph, be careful, the key point can be not only on a vertex, but also on an edge.
To make the problem more close to reality and easy to understand, imagine it’s a country where everybody wants to go aboard, say TC for example, and the key point is the only exit of this country to the outside colorful world. The N vertices can be treated as cities, M edges as roads. And if the key point is chosen, everyone in every city will choose a shortest path to the key point, and leave this country as if one second more will erase the purity and dignity.
But one last thing, visa. To simplify the problem, we already change the ID order and only the last K vertices have a visa office. One may choose any of those cities to get a visa. Of course, they will choose a visa-city to make the total length as short as possible.
And now, we come back to handle the original problem, where should the key vertex be? There are also two viewpoints for judging where the most perfect place is. We use Di to record the minimum cost for people in city i to get a visa and reach the key point, and Pi people in this city. The first opinion claims the Max(Di * Pi) to be as small as possible, while the second claims the Sum(Di * Pi) to be as small as possible. Your task is to solve both of these requests.
For each request, report the minimum value it claims, and then, report the place it can choose to achieve that value. If more than one such place, report INFINITE instead (you may assume the people in TC only know 0 and 1, other numbers are just infinite for them).
If you need to report a chosen place for key point, report the first edge id (1-based) the point appears, and then the distance between the point and the first vertex. For example, if there is only an edge , and the key point lies in vertex 1, report (1, 0.000).
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case includes three integers N, M, K. Then a line with N integers Pi follows. Then M lines following, each line contains three integers Ai, Bi, Ci, describing an undirected road. You can assume there is as least one path between any city pair.
Technical Specification
1. 1 <= T <= 64
2. 1 <= K < N <= 32
3. 0 <= Pi <= 1024
4. N - 1 <= M <= 512
5. 1 <= Ci <= 1024
6. 1 <= Ai, Bi <= N, Ai != Bi, no edge pair appears more than once.
Output
For each test case, output the case number in the first line. Then two lines, the first line describe the max request, and the second describe the sum request, as the format in the description.
Separate them by exactly one space, print “INFINITE” without quote if needed, and round all the floating numbers to three fractional digits. Refer to the sample output for more details.
Even more than one such place, you should report the minimum value it claims first.
Sample Input
2
3 3 1
1 2 3
1 2 1
2 3 2
1 3 3
4 4 2
3 2 1 1
1 2 2
2 3 2
3 4 2
4 1 2
Sample Output
Case 1:
4.000 2 2.000
7.000 2 2.000
Case 2:
7.200 3 1.600
16.000 3 2.000
