Toll Management

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:

1. Ai: The maximum amount of toll they can add to the i-th highway so that Hashmat’s set remains special.
2. Bi: The maximum amount of toll they can decrease from the i-th highway so that Hashmat’s set remains special. In other words, if Ci is the current toll of the i-th highway, then if the Government updates the toll of the highway to Ci + Ai (or Ci − Bi), Hashmat’s set remains special. Please note, while finding out Ai and Bi other tolls remain unchanged. This time Hashmat does not want to help the Government. He thinks this is a conspiracy against the people of Byteland. So they came to you. Will you help them to find out Ai and Bi for all the highways? Input First line of the input contains a positive integer T (T < 25), denoting the number of test cases. First line of each test contains two integer numbers N and M (1 ≤ N ≤ 10000, N −1 ≤ M ≤ 100000), denoting the number of city and number of highway respectively. Each of the next M lines contains the description of a highway, where the i-th line contains three integer numbers Ui, Vi and Ci (1 ≤ Ui,Vi ≤ N, Ui ̸= Vi, 0 ≤ Ci ≤ 1000), that means there is a highway between city Ui and city Vi and the toll of the highway is Ci. You may consider the highways to be bidirectional. Note that the first N − 1 highways in the input are the special highways. You may assume that there will be no invalid data in the input file. Output For each test case, output the test case number and a single integer S, where ∑M S = (i∗Ai +i2 ∗Bi) i=1

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