Cho đồ thị có hướng ~n~ đỉnh và ~m~ cạnh, một cạnh ~u~ và ~v~ sẽ mở 1 đường đi từ ~u~ tới ~v~ với thời gian là ~w~. Tấn sẽ xuất phát từ đỉnh 1 và Tân sẽ xuất phát tại một đỉnh ~p~ (~2 \le p \le n~), cả Tấn và Tân đều có thể di chuyển tự do qua các đỉnh, với mỗi đỉnh ~p~ mà Tân có thể xuất phát hãy tìm thời gian ngắn nhất để Tân với Tấn gặp nhau.

Yêu cầu: Với mỗi đỉnh ~p~ từ 2 đến ~n~, hãy tìm thời gian ngắn nhất để Tấn và Tân gặp nhau.

Input

• Dòng đầu tiên gồm 2 số nguyên ~n, m~ (~1 \le n \le 10^5, 1 \le m \le 2 \times 10^5~).
• ~m~ dòng sau, dòng thứ ~i~ chứa 3 số nguyên ~u_i, v_i, w_i~ thể hiện có cạnh nối giữa 2 đỉnh ~u_i~ và ~v_i~ với thời gian là ~w_i~ (~1 \le u_i, v_i \le n~).

Output

• Ghi ra ~n - 1~ số ứng với đáp án cần tìm cho các đỉnh xuất phát của Tân từ 2 đến ~n~.

Sample Input 1

5 7
1 2 2
2 4 1
4 1 4
2 5 3
5 4 1
5 2 4
2 1 1

Sample Output 1

1 -1 3 4