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.

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)

提交代码