Cho đồ thị vô hướng có trọng số gồm ~N~ đỉnh và ~M~ cạnh, nhiệm vụ của bạn là tìm đường đi ngắn nhất từ đỉnh 1 đến tất cả các đỉnh còn lại.

Input:

• Dòng đầu tiên chứa hai số nguyên ~N~, ~M~.

• M dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~,~v~ và ~w~ tương ứng là có cạnh nối giữa hai đỉnh ~u~, ~v~ và trọng số của cạnh là ~w~.

Output:

• Ghi ra khoảng cách từ đỉnh 1 đến các đỉnh còn lại, in ra 1000000000 nếu không có đường đi từ đỉnh 1 đến đỉnh đang xét.

Ràng buộc

• ~1 \le N \le 10^4~

• ~1 \le M \le 10^6~

• ~1 \le u,v \le N

• ~1 \le w \le 1000~

Ví dụ:

Input

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

Output

5 2 3 7