Đường đi đặc biệt (Minimum Path)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một đồ thị vô hướng, liên thông, có trọng số dương gồm $n$ đỉnh và $m$ cạnh. Đồ thị không có khuyên và không có hai cạnh nối cùng một cặp đỉnh.

Với một đường đi gồm các cạnh có trọng số $w_1,w_2,\ldots,w_k$, định nghĩa trọng số của đường đi là

Với mỗi đỉnh $i$ từ $2$ đến $n$, hãy tìm trọng số nhỏ nhất của một đường đi từ đỉnh $1$ đến đỉnh $i$ theo định nghĩa trên.

Input

Dòng đầu chứa hai số nguyên $n,m$.

Trong $m$ dòng tiếp theo, mỗi dòng chứa $v_i,u_i,w_i$, mô tả một cạnh vô hướng.

Đồ thị liên thông, không có khuyên và không có cạnh trùng.

Output

In $n-1$ số nguyên. Số thứ $i-1$ là trọng số nhỏ nhất của một đường đi từ đỉnh $1$ đến đỉnh $i$, với $2\le i\le n$.

Subtask

Trong tất cả các Subtask: $2\le n\le2\cdot10^5$; $1\le m\le2\cdot10^5$; $1\le v_i,u_i\le n$; $v_i\ne u_i$; $1\le w_i\le10^9$; đồ thị liên thông, không có khuyên và không có cạnh trùng.

• Subtask 1 — 10%: Mọi cạnh đều có trọng số $w_i=1$.
• Subtask 2 — 20%: Đồ thị là một cây, tức $m=n-1$.
• Subtask 3 — 30%: $n\le300$; $m\le2000$.
• Subtask 4 — 40%: Không có điều kiện bổ sung.

Ví dụ

Input

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

Output

1 2 2 4

Giải thích

Bốn số lần lượt là giá trị nhỏ nhất của đường đi đặc biệt từ đỉnh $1$ đến các đỉnh $2,3,4,5$.