Cây khung nhỏ thứ nhì

Bạn được cung cấp một đồ thị vô hướng liên thông gồm \(N\) đỉnh và \(M\) cạnh. Hãy tìm cây khung nhỏ thứ nhì của đồ thị.

Cây khung nhỏ thứ nhì là cây khung có tổng trọng số nhỏ nhất kế tiếp so với cây khung nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N, M\) \((1 \leq N \leq 10^5, 1 \leq M \leq 10^5)\) --- số lượng đỉnh và cạnh của đồ thị.
• \(M\) dòng tiếp theo mô tả danh sách các cạnh của đồ thị. Mỗi dòng chứa ba số nguyên \(u_i, v_i, w_i\) \((1 \leq u_i, v_i \leq N, 1 \leq w_i \leq 10^9)\), biểu thị một cạnh giữa hai đỉnh \(u_i\) và \(v_i\) với trọng số \(w_i\).

Output

Một số nguyên duy nhất là giá trị của cây khung nhỏ thứ nhì. Nếu không tồn tại, in ra -1.

Example

3 3
1 2 1
3 1 1
3 2 1

2

3 3
1 2 3
3 1 1
3 2 2

4

Scoring

• (\(50\%\) số điểm) \(1 \leq N \leq 500\), \(1 \leq M \leq 10^3\)
• (\(50\%\) số điểm) \(1 \leq N, M \leq 10^5\)