Khoảng Cách Từ Đỉnh Đầu

Cho một đồ thị có hướng gồm $n$ đỉnh, được đánh số từ $1$ đến $n$. Mỗi cạnh có một độ dài nguyên dương. Từ đỉnh $1$, luôn tồn tại ít nhất một đường đi tới mọi đỉnh còn lại.

Hãy tính độ dài đường đi ngắn nhất từ đỉnh $1$ tới từng đỉnh của đồ thị.

Input

• Dòng đầu chứa hai số nguyên $n$ và $m$ - số đỉnh và số cạnh.
• Mỗi dòng trong $m$ dòng tiếp theo chứa ba số nguyên $a,b,c$, biểu thị một cạnh có hướng đi từ $a$ tới $b$ với độ dài $c$.

Output

• In $n$ số nguyên. Số thứ $i$ là độ dài đường đi ngắn nhất từ đỉnh $1$ tới đỉnh $i$.

Constraints

• $1\le n\le 10^5$.
• $1\le m\le 2\cdot 10^5$.
• $1\le a,b\le n$.
• $1\le c\le 10^9$.
• Có thể có khuyên và nhiều cạnh cùng hướng nối một cặp đỉnh.
• Từ đỉnh $1$ đi được tới mọi đỉnh.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 30$ và $m\le 200$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5 8
1 2 7
1 3 2
3 2 1
2 4 4
3 4 8
4 5 3
3 5 20
2 5 10

0 3 2 7 10