Đường đi nhỏ nhất

Cho một đồ thị vô hướng liên thông có trọng số 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.

Trọng số của một đường đi gồm $k$ cạnh mang chỉ số $e_1,e_2,\dots ,e_k$ được định nghĩa là

$$\sum _{i=1}^k{w}_{e_i}-{max}_{i=1}^k{w}_{e_i}+{min}_{i=1}^k{w}_{e_i}$$

với $w_j$ là trọng số của cạnh thứ $j$ trong đồ thị. Nói cách khác, ta lấy tổng trọng số các cạnh trên đường đi, bỏ đi một lần cạnh nặng nhất và cộng thêm một lần cạnh nhẹ nhất.

Đường đi ở đây là một dãy cạnh nối tiếp nhau bất kỳ: một đỉnh hoặc một cạnh được phép xuất hiện nhiều lần. Nếu một cạnh được đi qua nhiều lần thì mỗi lần đi qua được tính là một phần tử riêng của dãy $e_1,e_2,\dots ,e_k$.

Với mỗi $i$ ($2\le i\le n$), hãy tìm trọng số nhỏ nhất của một đường đi từ đỉnh $1$ đến đỉnh $i$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ là số đỉnh và số cạnh của đồ thị.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $v_i$, $u_i$, $w_i$ là hai đầu mút và trọng số của cạnh thứ $i$.

Dữ liệu ra

In ra $n-1$ số nguyên: trọng số nhỏ nhất của đường đi từ đỉnh $1$ đến đỉnh $i$, lần lượt với $i=2,3,\dots ,n$.

Ràng buộc

• $2\le n\le 5·{10}^4$
• $1\le m\le 5·{10}^4$
• $1\le v_i,u_i\le n$ và $v_i\ne u_i$
• $1\le w_i\le {10}^9$
• Đồ thị liên thông và không có hai cạnh nối cùng một cặp đỉnh.

Ví dụ