Toll Management (III)

Government of Byteland is not happy with their yearly money collection and revenue this year. They have imposed several taxes and VATs here and there. This time the Government is going to increase the toll on highways of the country. But people of Byteland are very much dissatisfied with the Government’s taxation and revenue generation policies. So Government is rethinking their policies. There are N cities and M highways in Byteland. Each highway directly connects two different cities. Government has fixed a toll for each highway and whoever passes the highway have to pay the toll. Government wants to increase the toll from next month. But as they don’t want to dissatisfy the people of Byteland anymore, they came up with a unique idea. They will change (increase or decrease) the toll of some highway such that the shortest path cost from the capital to any other city will remain same as now. So they want to know two information for each i-th highway:

1. Ai: What is the maximum amount of toll they can increase without affecting the shortest path cost from capital city to all other cities?
2. Bi: What is the maximum amount of toll they can decrease without affecting the shortest path cost from capital city to all other cities? In other words, if Ci is the current toll of highway i, then if the Government updates the toll of the highway to Ci +Ai (or Ci −Bi), the shortest path cost from capital city to city 1,2,...,N does not change at all. Note that the Government is not imposing the new toll right away, they just want to estimate the A and B values of each highway. So when estimating the A and B values of a highway, there is no new toll imposed on any highway. As you are the great programmer of Byteland, you are going to help the Government of Byteland to find Ai and Bi values for each i-th highway (for 1 ≤ i ≤ M). Input First line of the input contains a positive integer T (T < 10), denoting the number of test cases. First line of each test contains two integer numbers N and M (2 ≤ N ≤ 10, 000, 1 ≤ M ≤ 100, 000), 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 ≤ 1,000), that means there is a highway from city Ui to city Vi and the toll of the highway is Ci. All the highways are directional, that means if there is a highway from city x to city y, not necessarily there exist a highway from city y to x, unless it is mentioned explicitly. Note that the city numbered 1 is the capital city of Byteland and every other city (2 to N), will be reachable from the capital city. Output For each test case, output the test case number and a single integer S, where ∑M S = If the value of Ai or Bi is infinite then replace the value with ‘-1’. The answer will be such that it will fit into 64-bit signed integer. Note: Explanation of the sample test cases: For the first test case, (A1, B1) = (00), (A2, B2) = (00), (A3, B3) = (−10) and (A4, B4) = (−10). For the second test case, (A1, B1) = (00), (A2, B2) = (00), (A3, B3) = (00) and (A4, B4) = (−1, 1). i=1 i∗Ai +i2 ∗Bi

2/2 Sample Input 2 44 125 135 245 345 44 125 135 244 345 Sample Output Case 1: -7 Case 2: 12