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