Another attempt of revising toll system is rejected by the people of Byteland. The Government is in big trouble now. They are seeking help of Hashmat, the brave warrior and the great programmer of Byteland to solve the problem. Hashmat has come up with a new idea to fix this toll management problem. There are N cities and M bidirectional highways among these cities. The government proposed some toll (may be different toll for different highways) for each of the highways. But people think they are being over charged. Hashmat’s idea was to make both the people and the Government happy. In his plan he decided to keep the toll of the highways as it is in Government’s proposal but he would publish a special set of N − 1 highways. There are two conditions for a set of N − 1 highways to be special. These N − 1 highways have to connect all the cities and a person will be able to go from a city to any other city spending minimum toll in any of these highways. Please note, using these special highways does not guarantee minimum sum of toll but it guarantees you minimum individual toll. People of Byteland are happy with the idea of special highway, but the Government is not happy as they want more toll from the highway sector. They called up a meeting and formed a committee to find two values for all the highways. Let these values be Ai and Bi for the i-th highway and defined as follows:
2/2 If the value of Ai or Bi is infinite, replace the value with ‘-1’. Illustration: In the figures below the dashed lines are normal highway and the solid lines are special highway. Illustration of first sample input Sample Input 2 33 125 237 1 3 10 45 131 342 123 144 245 Sample Output Case 1: 30 Case 2: 72 Illustration of second sample input