General Broken Arrow and Lieutenant General Shadow Coder are two great warriors of Gigaland. Every year they fought several wars together like ICPC, NCPC etc. The peoples of Gigaland were living happily until one day the king of Gigaland General Rem (RIP) died. Now both Broken Arrow and Shadow Coder wants to become the new king of Gigaland. As this is not possible for two persons to become king of a country at the same time, they leave it to the field of war. They decided to fight each other in the Great Chaos Jam (GCJ) field and the winner will become the new king. Colonel Dragoon, friend of both Broken Arrow and Shadow Coder wants to avoid the blood shedding war and comes up with a great solution. According to his proposed solution the country will be divided into two disjoint sets of cities, called A and B. Broken Arrow will rule the cities in the set of A and Shadow Coder will rule the rest of the cities. But the people of Gigaland will get frustrated and angry with these divisions. To make peoples remain calm and happy Dragoon thought another idea. They will build a sub-country of Gigaland called Megaland consist of some cities and connecting roads of Gigaland so that peoples from set A and B can have some access to other cities. Though cities of set A and B are disjoint, cities might not be disjoint between Megaland and set A and between Megaland and set B. Broken Arrow and Shadow Coder both agreed with the idea of Dragoon. The country of Gigaland consists of N (numbered from 1 to N) cities and M bidirectional roads each of which connects two different cities and each road has a cost to travel. Gigaland was built such a way that every city is connected to each other with sequence of one or more roads. Set A will consists of first K (2 ≤ K ≤ min(N,50)) cities, 1,2,...,K numbered cities of Gigaland and rest N − K cities will belong to the set B. Though the warriors have agreed to build the new sub-country Megaland, they have some conditions. Each city of set A should be incident to odd number of roads of Megaland and each city of set B should be incident to even number (possibly zero) of roads of Megaland. The cost of road system in Megaland should be minimum, which is sum of all the road cost of Megaland should be minimized. The cities of Megaland might or might not be connected to each other. In terms of graph theory, you are given a weighted graph G = (N,M), two set of nodes A = {1,2,...,K} and B = {K +1,K +2,...,N}. You have to find the minimum cost sub-graph S (subset of edges), where each node in A should have odd degree in S and each node in B should have even degree in S. Here cost of S, is sum of all the edge cost in S. Given N, M, K and description of M roads of Gigaland, find the minimum possible cost of sub- country Megaland. Input Input starts with a positive integer, T (T ≤ 50) denoting the number of test cases. Each case starts with three integers, N (2 ≤ N ≤ 100), M (N − 1 ≤ M ≤ N ∗ (N − 1)/2) and K (2 ≤ K ≤ min(N, 50)). Each of the next M lines contains three integers u, v and c (1 ≤ u,v ≤ N, u ̸= v, 0 < c < 10000) meaning that there is a bidirectional road between city u and v of cost c. No two roads will be same. Output For each test case, print the test case number (starting from 1) and the minimum possible cost of Megaland if it is possible to build the sub-country according to the conditions described above, otherwise print ‘Impossible’.
2/2 Explanation For test case 1, In Megaland degree of each node in set A = {1,2,3,4} is 1 and degree nodes in set B = {5,6,7} are 2, 2 and 0 respectively. Sample Input 2 774 1 7 10 151 252 363 461 564 378 443 121 131 241 341 Sample Output Case 1: 7 Case 2: Impossible