Có ~N~ thành phố và ~M~ chuyến bay kết nối giữa chúng. Bạn đang ở thành phố số 1. Nhiệm vụ của bạn là tìm khoảng cách ngắn nhất tới các thành phố còn lại

Input

Dòng đầu tiên chứa hai số nguyên ~N~, ~M~: số thành phố và số chuyến bay giữa chúng.

~M~ dòng tiếp theo, mỗi dòng gốm 3 số nguyên ~a~, ~b~, ~c~, biểu diễn là có một chuyến bay xuất phát tại thành phố ~a~, hạ cánh ở thành phố ~b~ và có độ dài bằng ~c~.

Mỗi chuyến bay là chuyến bay một chiều.

Output

In ra ~N~ số nguyên, khoảng cách từ thành phố thứ nhất tới tất cả ~N~ thành phố.

Giới hạn

~1 <= N <= 10^5~

~1 <= M <= 2*10^5~

~1 <= a, b <= N~

~1 <= c <= 10^9~

Test mẫu

Input:

3 4
1 2 6
1 3 2
3 2 3
1 3 4

Output:

0 5 2