There are N cities and Demon is in city 1. Now, there are M pair of roads between some cities and each of the roads have cost to travel by it. The cost to travel from city c₁ to c_k is 1*w₁ + 2*w₂ + 3*w₃+......+(k-1)*w_k-1 where w_i is the cost to travel from city p_i to city p_i+1. Demon is lazy and so he wants you to find the minimum cost to travel from city 1 to every other city from 1 to N. If there exists no path to travel from city 1 to city i, print -1.

Note: There can be self-loop roads or multiple edge roads. All the roads are bidirectional.

Input:
The first line contains two space-separated integers n and m - the number of nodes and edges respectively. The next m lines contain three space-separated integers x, y, and w - representing an edge between x and y with cost w

Constraints:
1<=n<=3000
0<=m<=10000
1<=x,y<=n
1<=w<=1e9

Output:
Output n lines. In the i^th line, output the minimum distance from city 1 to the i^th city. If there exists no such path, output -1.