bgb chuyển nhà đến một trang trại nhỏ, nhưng cậu ấy thường xuyên quay lại trang trại của bạn bè. Vì rất thích phong cảnh ven đường và không muốn chuyến đi kết thúc quá nhanh, mỗi lần đi từ trang trại \(1\) đến trang trại \(N\), bgb chọn đường đi ngắn thứ hai thay vì đường đi ngắn nhất.

Cho một đồ thị vô hướng có trọng số gồm \(N\) đỉnh và \(M\) cạnh. Cạnh thứ \(i\) nối hai đỉnh \(u_i, v_i\) và có độ dài \(w_i\).

Một đường đi từ \(1\) đến \(N\) có thể đi qua cùng một đỉnh hoặc cùng một cạnh nhiều lần.

Hãy tìm độ dài của đường đi ngắn thứ hai nghiêm ngặt từ \(1\) đến \(N\), tức là độ dài nhỏ nhất trong các đường đi có độ dài lớn hơn nghiêm ngặt độ dài đường đi ngắn nhất từ \(1\) đến \(N\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N, M\).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\), mô tả một cạnh vô hướng giữa \(u\) và \(v\) có độ dài \(w\).

Output

• In ra một số nguyên duy nhất: độ dài đường đi ngắn thứ hai nghiêm ngặt từ \(1\) đến \(N\).

Constraints

• \(2 \le N \le 2 \cdot 10^5\)
• \(1 \le M \le 2 \cdot 10^5\)
• \(1 \le u, v \le N\)
• \(u \neq v\)
• \(1 \le w \le 5000\)
• Có ít nhất một đường đi từ \(1\) đến \(N\).
• Có thể có nhiều cạnh nối cùng một cặp đỉnh.

Example

4 4
1 2 100
2 4 200
2 3 250
3 4 100

450

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

4

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 500, M \le 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \le 5000, M \le 5000\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc bổ sung.