Đất nước Byteland có \(n\) thành phố được đánh số từ \(1\) đến \(n\). Các thành phố này được kết nối với nhau bởi \(m\) tuyến đường cao tốc một chiều. Ngọc Linh đang ở thành phố \(1\) và cô ấy muốn chọn một thành phố lý tưởng để du lịch trong kỳ nghỉ hè sắp tới. Một thành phố lý tưởng phải vừa đủ gần thành phố \(1\) và cũng phải vừa đủ thú vị để xứng đáng với thời gian mà Linh bỏ ra. Vì chưa đủ thì giờ để cân nhắc về tiêu chuẩn thứ nhì (độ thú vị) nên trước mắt cô ấy chỉ cần biết quãng đường ngắn nhất từ chỗ cô ấy đến từng thành phố trong đất nước Byteland (thông qua các tuyến đường cao tốc) là bao nhiêu. Các bạn hãy lập trình tính toán giúp Ngọc Linh nhé!

Input

Dòng đầu chứa hai số nguyên dương \(n\) và \(m\) lần lượt là số thành phố và số tuyến đường cao tốc một chiều.

Mỗi dòng trong \(m\) dòng tiếp theo chứa ba số nguyên dương \(a\), \(b\) và \(c\) thể hiện một tuyến đường cao tốc một chiều nối thành phố \(a\) và thành phố \(b\) với độ dài \(c\). Dữ liệu luôn đảm bảo tồn tại đường đi từ thành phố \(1\) đến tất cả các thành phố còn lại.

Output

\(n\) số nguyên là độ dài đường đi ngắn nhất từ chỗ Ngọc Linh đến các thành phố \(1\), \(2\), \(3\),..., \(n\).

Ví dụ

Sample input

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

Sample output

0 5 2

Giới hạn

• \(1\leq n\leq 10^5\).
• \(1\leq m\leq 2.10^5\).
• \(1\leq a, b\leq n\).
• \(1\leq c\leq 10^9\).