Cho đồ thị có hướng, có trọng số gồm ~n~ đỉnh và ~m~ cạnh. Với mọi đỉnh ~i~ ~(1 \le i < n)~, yêu cầu tìm độ dài đường đi ngắn nhất từ đỉnh ~i~ đến đỉnh ~n~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(2 \le n,m \le 10^5)~.
• ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u,v,w~ ~(1 \le u,v \le n,~ ~1 \le w \le 10^9)~ biểu thị đường đi từ ~u~ đến ~v~ có trọng số ~w~.
• Dữ liệu đảm bảo luôn tồn tại đường đi từ mọi đỉnh ~i~ ~(1 \le i < n)~ đến đỉnh ~n~.

Output

• In ra trên ~n-1~ dòng, dòng thứ ~i~ là độ dài đường đi ngắn nhất từ đỉnh ~i~ đến đỉnh ~n~.

Samples

Sample Input 1

3 6
1 2 3
2 3 1
1 3 5
2 1 3
3 2 1
3 1 5

Sample Output 1

4
1