There was a strange city with n junctions connected by m bidirectional roads. Even though the rapid growth of ride-sharing companies became a blessing for the general public, it also became a nightmare for the traditional taxi companies. So, they decided to come up with a scheme to stop this immense growth.

For simplicity, assume that a driver earns a static w_i amount passsing a road. Roads form loops, loop is a set of distinct junctions j₁, j₂, …, j_k except j₁ = j_k, k > 3 and (j_i, j_{i + 1}) (1 ≤ i < k) are connected by a road.

For each road, they want to set a minimum amount of toll (integer) such that there exists a loop containing the road and if a driver visits the roads in that loop in the same order, he/she needs to pay more tolls than the total earned money in the loop.

Input starts with a positive integer T (≤ 50), denoting the number of test cases.

Each case starts with a blank line. The next line contains two integers n m (1 ≤ n ≤ 200, 0 ≤ m). Assume that the junctions are identified as integers. Each of the next m lines will contain three integers u v w (0 ≤ u, v < n, u ≠ v, 0 < w ≤ 200), meaning that a driver earns w if he/she visits road connecting junction u and v. There is at most one road between any two junctions.

For each case, print the case number in a single line. Then for each road in the city (in the order of input), print the minimum possible toll for that road. If it's not possible, print impossible.

• Dataset is huge, use faster I/O methods.

For case 1, for the first road 0 - 1, if a toll of 52 is set to the road, then if a driver passes 0 - 1 - 2 - 3 - 0 (earning: -52 + 20 + 16 + 15 = -1); he/she is paying more toll than earning.
For case 2, for the second road 1 - 2, if a toll of 28 is added to the road, then if a driver passes 3 - 1 - 2 - 3 (earning: 11 - 28 + 16 = -1); he/she is paying more toll than earning.