Có \(n\) thành phố và có \(m\) chuyến xe đi qua lại giữa các thành phố. Hãy tìm độ dài đường đi ngắn nhất từ thành phố \(1\) đến tất cả thành phố.

Input

• Dòng đầu tiên gồm \(2\) số nguyên \(n,m\).
• \(m\) dòng tiếp theo, mỗi dùng gồm \(3\) số nguyên \(u,v,c\), thể hiện đường đi từ \(u\) đến \(v\) có độ dài là \(c\). Lưu ý, tất cả đường đi là một chiều. Giả sử, có đường đi đến tất cả thành phố.

Output

• In ra \(n\) số nguyên là độ dài đường đi từ thành phố \(1\) đến tất cả thành phố còn lại

Điều kiện

• \(1 \le n \le 10^5\)
• \(1 \le m \le 2 \times 10^5\)
• \(1 \le u,v \le n\)
• \(1 \le c \le 10^9\)

Sample Input 1

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

Sample Output 1

0 5 2