Đường đi ngắn nhì

Cho đồ thị có hướng gồm $N$ đỉnh, $M$ cung (có trọng số là độ dài cung). Đường đi được phép đi qua một đỉnh hoặc một cung nhiều lần (kể cả đi qua đỉnh $N$ rồi quay lại), độ dài đường đi là tổng độ dài các cung trên đường đi, cung đi qua nhiều lần được tính nhiều lần.

Gọi $D$ là độ dài đường đi ngắn nhất từ $1$ đến $N$. Độ dài đường đi ngắn nhì là độ dài nhỏ nhất lớn hơn hẳn $D$ trong số độ dài các đường đi từ $1$ đến $N$ (nhiều đường đi khác nhau có cùng độ dài $D$ không làm thay đổi đáp án).

Yêu cầu: Tìm độ dài đường đi ngắn thứ nhì từ $1$ đến $N$.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N,M$ ($2\le N\le 20000$; $0\le M\le {10}^5$).
• $M$ dòng tiếp theo, mỗi dòng ghi $3$ số nguyên dương $a,b,d$ tương ứng là có đường đi một chiều từ $a$ đến $b$ và độ dài bằng $d$ ($1\le a,b\le N$; $1\le d\le {10}^5$). Có thể có nhiều cung giữa cùng một cặp đỉnh và có thể có cung từ một đỉnh đến chính nó.

Các số cách nhau ít nhất một dấu cách.

Dữ liệu ra

In ra một số duy nhất là độ dài đường đi ngắn nhì. Nếu không có đường đi ngắn nhì (kể cả khi không có đường đi nào từ $1$ đến $N$) thì in ra $-1$.

Ràng buộc

• $2\le N\le 20000$.
• $0\le M\le {10}^5$.
• $1\le a,b\le N$, $1\le d\le {10}^5$.

Subtasks

• Có $30\%$ số test ứng với $N\le 10$, $M\le 40$.
• Có $30\%$ số test ứng với $10<N\le 40$, $M\le 1000$.
• Các test còn lại ứng với $N\ge 1000$.

Ví dụ