Trọng số đường đi

Bạn được cung cấp một đồ thị vô hướng, có trọng số và liên thông, bao gồm \(n\) đỉnh và \(m\) cạnh. Đảm bảo rằng đồ thị không có khuyên (self-loops) và các cạnh lặp.

Định nghĩa trọng số của một đường đi:

Giả sử đường đi có \(k\) cạnh với các chỉ số \(e_1, e_2, \ldots, e_k\). Trọng số của đường đi được xác định bởi công thức:

\(\text{weight of path} = \sum_{i=1}^k w_{e_i} - \max_{i=1}^k w_{e_i} + \min_{i=1}^k w_{e_i}\)

Nhiệm vụ:

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

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((2 \leq n \leq 2 \cdot 10^5; 1 \leq m \leq 2 \cdot 10^5)\) --- số đỉnh và số cạnh của đồ thị.
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(v_i, u_i, w_i\) \((1 \leq v_i, u_i \leq n; 1 \leq w_i \leq 10^9; v_i \neq u_i)\) --- các đỉnh của cạnh thứ \(i\) và trọng số tương ứng.

Output

• In \(n-1\) số nguyên trên một dòng, mỗi số tương ứng với trọng số nhỏ nhất của đường đi từ đỉnh \(1\) đến đỉnh \(i\) \((2 \leq i \leq n)\).

Example

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

1 2 2 4 

6 8
3 1 1
3 6 2
5 4 2
4 2 2
6 1 1
5 2 1
3 2 3
1 5 4

2 1 4 3 1 

7 10
7 5 5
2 3 3
4 7 1
5 3 6
2 7 6
6 2 6
3 7 6
4 2 1
3 1 4
1 7 4

3 4 2 7 7 3 

Scoring

• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n, m \leq 10\).

• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n, m \leq 100\).

• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n, m \leq 500\), \(w_{i}= a\) hoặc \(w_{i} = b\) với \(a\), \(b\) là hằng số.

• \(25\%\) số test tương ứng với \(25\%\) số điểm còn lại không có ràng buộc gì thêm.