Dystopia consists of N cities. There are one-way roads connecting some pairs of cities. The dysfunctional state has recently seen a lot of protests to overthrow the tyrannical ruler and the government plans to use military patrol vehicles to make sure that the protests are suppressed. Every patrol vehicle is assigned a sequence of cities. If a patrol vehicle is assigned the cities c₁, c₂ ... c_k then it starts from the city c₁ and takes the direct one-way road to c₂, from there it takes the one-way road to c₃ and so on. Finally the vehicle takes the one way road from c_k to c₁. This routine is repeated everyday to keep the protestors perpetually under fear.

Now note that:

• Every city has to appear in exactly one vehicle's patrol sequence exactly once
• Every patrol vehicle has to move - so it has to be assigned more than one city

The government does not have any limit on the number of patrol vehicles it can use. However, they want to make sure that the least possible amount of money is spent on the patrol mission and hence they want to minimise the total distance travelled by the patrol vehicles.

Given the road network of Dystopia, find the minimum total distance the patrol vehicles need to move so that all the cities can be patrolled. If it is impossible to organise a nationwide patrol with the given constraints, report the same.

Input

First line of the contains T, the number of test cases (T<=10)

This is followed by the descriptions of the T testcases. The first line of the description contains two integers N and R, the number of cities and one way roads respectively (N<=200, R<=10000). The cities are numbered 1, 2, 3 ... N This is followed by R lines, each representing a one way road by 3 integers N₁, N₂ and D : the start city, the end city and the length of the road respectively (N₁ != N₂, 1 <= D <= 1000000). You are assured that there is no more than one one way road from any N₁ to N₂

Output

For each test case output one line. If the patrol can be done, output the minimum total distance that the patrol vehicles have to travel. Otherwise output Impossible

Example

Input:
2
3 3
1 2 1
2 3 1
1 3 1
4 6
1 2 2
2 3 2
3 4 2
4 1 2
1 4 1
3 2 1

Output:
Impossible
6