B'Polycarp is developing an RPG game where the main character fights monsters and searches for treasure in dungeons. Now Polycarp is making one of the dungeons the character can explore. The dungeon consists of n rooms connected by m two-way tunnels, and it is possible to reach every room from every other room using tunnels. The rooms are guarded by monsters (the number of monsters in the i -th room is a_i ), and the tunnels contain gold coins (the number of coins in the i -th tunnel is w_i ). The i -th two-way tunnel connects rooms v_i and u_i . Polycarp has already fixed the number of coins in each tunnel (the values of w_i are already known), and now he tries to place the monsters in the rooms (the values of a_i are not known yet). Polycarp wants to choose the number of monsters in each room in such a way that the following two conditions are met: Help Polycarp to choose the values a_1 , a_2 , ..., a_n , or tell him that it is impossible and he has to change something in his dungeon plan. The first line contains one integer t ( 1 <= t <= 100000 ) -- the number of test cases. Then the test cases follow. The first line of each test case contains two integers n and m ( 2 <= n <= 200000 ; n - 1 <= m <= min(200000, frac{n(n-1)}{2}) ) -- the number of rooms and tunnels in the dungeon, respectively. Then m lines follow, each line describing one of the tunnels in the dungeon. The i -th line contains three integers v_i , u_i and w_i ( 1 <= v_i, u_i <= n ; v_i ne u_i ; 1 <= w_i <= 10^9 ) denoting a two-way tunnel that connects rooms v_i and u_i , and contains w_i coins. The tunnel system is connected in each test case (it is possible to reach every room from every other room using the tunnels). Each pair of rooms is connected by at most one tunnel. The sum of n over all test cases d'...