DanDan like travling

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

DanDan is a smart girl,and she likes travling.Holiday is coming.So she wants to travel to America from China.With so many ways to America,she wants to choose the shortest.So she asks you to help.

Input

The first line contains an integer t ( 1 <= t <= 10 ): the number of test cases. Then for each test case:The first line contains two integers n and m,where n ( n <= 10000 ) is the number of countries and m ( m <= 100000 )is the number of roads.Then next m lines each contains three elements A,B and C,that means the length from A to B is C and from B to A is also C.(The length of A and B is less than 100,C<=100)

Output

For each test case, output the result in the form of sample.You should print the case number and the shortest length she will choose.If she can not arrive America,output "impossible!".

Sample Input

2
3 2
China Huodongshi 10
Huodongshi America 10
3 1
China Huodongshi 10

Sample Output

Case 1: 20
Case 2: impossible!

Hint

None

Source

陶翔专场练习赛

提交代码