There is a deadly war going on between two countries (Bitland and Byteland) in the wizarding world. They are fighting with each other in a large forest. There are some strategically important places in the forest known as Hubs. They have numbered all the Hubs with numbers 1 to n. There are roads in the forest where each road connects two Hubs. The army of Bitland want to reach Hub n starting from Hub 1 by travelling shortest possible distance. They also know that there is at most one road between any two hubs and found the shortest path from Hub 1 to n.
Unfortunately, the spies of Byteland came to know their plan, but they were not sure about the details of any specific path. So they did not want to take any risk and placed mines on any road which is a part of any shortest path from Hub 1 to Hub n. Now, Bitland also have spies working in Byteland, thus they also came to know about this trap. So, they decided to follow the shortest path which does not contain any of those roads.
The chief of army of Byteland could assume that their trap could be exposed to their enemy. Now, they have already used all the mines. So, they wanted to destroy roads (where no mines were placed) by bombing such that there would not be any path from Hub 1 to Hub n. But he is not sure whether they have enough bombs to do it. So he wants to destroy roads by bombing in such a way that the summation of those destroyed roads’ length is minimum, then he would estimate how many bombs are required to do it.
The first line of input contains a single integer, T (T ≤ 50). Then T test cases follow. Each case starts with the number of Hubs, n (2 ≤ n ≤ 300) and total number of roads, m (1 ≤ m ≤ 104). Then m lines follow, where each line contains three integers, u, v (1 ≤ u, v ≤ n) and w (1 ≤ w ≤ 104), indicating a road between Hub u and v with length w.
For each case, output “Case x: y z” in a separate line, where x is case number, y is the length of the shortest path the army of Bitland is going to follow and z is the summation of the length of the roads Byteland army chief wants to destroy. If there is no path from Hub 1 to Hub n before or after deploying the mines, print -1 as both of the values of y and z.
| Input | Output |
|---|---|
2 3 3 1 2 3 2 3 2 1 3 3 2 1 1 2 4 | Case 1: 5 2 Case 2: -1 -1 |