Để lập lộ trình xe đưa đón sinh viên giữa các cơ sở của Đại học Công nghiệp Hà Nội, Phòng Quản trị đã số hoá bản đồ thành ~n~ địa điểm (cổng trường, giảng đường, ký túc xá, bến xe buýt, …) đánh số từ ~1~ đến ~n~ và ~m~ tuyến đường hai chiều; tuyến đường thứ ~j~ nối trực tiếp hai địa điểm ~u_j~ và ~v_j~ và có độ dài ~w_j~ mét. Giữa hai địa điểm có thể có nhiều tuyến đường khác nhau. Mọi chuyến xe đều xuất phát từ địa điểm số ~1~; độ dài của một đường đi là tổng độ dài các tuyến đường mà nó đi qua.

Yêu cầu

Với mỗi địa điểm ~i~ (~1 \le i \le n~), hãy tìm độ dài của đường đi ngắn nhất từ địa điểm ~1~ đến địa điểm ~i~.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên ~n~ và ~m~;
• ~m~ dòng tiếp theo, dòng thứ ~j~ chứa ba số nguyên ~u_j~, ~v_j~, ~w_j~.

Kết quả ra

Ghi ra trên một dòng ~n~ số nguyên cách nhau bởi dấu cách; số thứ ~i~ là độ dài đường đi ngắn nhất từ địa điểm ~1~ đến địa điểm ~i~, hoặc ~-1~ nếu không có cách nào đi từ địa điểm ~1~ đến địa điểm ~i~. (Số thứ nhất luôn bằng ~0~.)

Ràng buộc

~1 \le n \le 10^5~; ~0 \le m \le 2 \cdot 10^5~; ~1 \le u_j, v_j \le n~; ~u_j \ne v_j~; ~1 \le w_j \le 10^9~.

• Subtask 1 (20% số điểm – test 01–04): ~n \le 100~ và ~m \le 1000~;
• Subtask 2 (20% số điểm – test 05–08): mọi ~w_j = 1~;
• Subtask 3 (20% số điểm – test 09–12): ~n \le 2000~ và ~m \le 5000~;
• Subtask 4 (40% số điểm – test 13–20): không có ràng buộc bổ sung.

Lưu ý: kết quả có thể vượt quá phạm vi kiểu số nguyên 32 bit.

Ví dụ

Dữ liệu vào mẫu 1

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

Kết quả ra mẫu 1

0 3 1 8 -1

Giải thích

Đường đi ngắn nhất tới địa điểm ~2~ là ~1 \to 3 \to 2~ với độ dài ~1 + 2 = 3~, ngắn hơn cả hai tuyến đường nối trực tiếp ~1~ với ~2~ (dài ~4~ và ~7~). Tới địa điểm ~4~: ~1 \to 3 \to 2 \to 4~ dài ~8~. Địa điểm ~5~ không có tuyến đường nào nên kết quả là ~-1~.