B"All of Slavic's friends are planning to travel from the place where they live to a party using their bikes. And they all have a bike except Slavic. There are n cities through which they can travel. They all live in the city 1 and want to go to the party located in the city n . The map of cities can be seen as an undirected graph with n nodes and m edges. Edge i connects cities u_i and v_i and has a length of w_i . Slavic doesn't have a bike, but what he has is money. Every city has exactly one bike for sale. The bike in the i -th city has a slowness factor of s_{i} . Once Slavic buys a bike, he can use it whenever to travel from the city he is currently in to any neighboring city, by taking w_i cdot s_j time, considering he is traversing edge i using a bike j he owns. Slavic can buy as many bikes as he wants as money isn't a problem for him. Since Slavic hates traveling by bike, he wants to get from his place to the party in the shortest amount of time possible. And, since his informatics skills are quite rusty, he asks you for help. What's the shortest amount of time required for Slavic to travel from city 1 to city n ? Slavic can't travel without a bike. It is guaranteed that it is possible for Slavic to travel from city 1 to any other city. The first line contains a single integer t ( 1 <= q t <= q 100 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains two space-separated integers n and m ( 2 <= q n <= q 1000 ; n - 1 <= q m <= q 1000 ) -- the number of cities and the number of roads, respectively. The i -th of the following m lines each contain three integers u_i , v_i , w_i ( 1 <= u_i, v_i <= n , u_i neq v_i ; 1 <= q w_i <= q 10^5 ), denoting that there is a road between cities u_i and v_i of length "...