B"Pak Chanek is playing one of his favourite board games. In the game, there is a directed graph with N vertices and M edges. In the graph, edge i connects two different vertices U_i and V_i with a length of W_i . By using the i -th edge, something can move from U_i to V_i , but not from V_i to U_i . To play this game, initially Pak Chanek must place both of his hands onto two different vertices. In one move, he can move one of his hands to another vertex using an edge. To move a hand from vertex U_i to vertex V_i , Pak Chanek needs a time of W_i seconds. Note that Pak Chanek can only move one hand at a time. This game ends when both of Pak Chanek's hands are on the same vertex. Pak Chanek has several questions. For each p satisfying 2 <= q p <= q N , you need to find the minimum time in seconds needed for Pak Chanek to end the game if initially Pak Chanek's left hand and right hand are placed on vertex 1 and vertex p , or report if it is impossible. The first line contains two integers N and M ( 2 <= q N <= q 10^5 , 0 <= q M <= q 2 cdot 10^5 ) -- the number of vertices and edges in the graph. The i -th of the next M lines contains three integers U_i , V_i , and W_i ( 1 <= U_i, V_i <= N , U_i neq V_i , 1 <= W_i <= 10^9 ) -- a directed edge that connects two different vertices U_i and V_i with a length of W_i . There is no pair of different edges i and j such that U_i = U_j and V_i = V_j . Output a line containing N-1 integers. The j -th integer represents the minimum time in seconds needed by Pak Chanek to end the game if initially Pak Chanek's left hand and right hand are placed on vertex 1 and vertex j+1 , or -1 if it is impossible. If initially Pak Chanek's left hand is on vertex 1 and his right hand is on vertex $"...