Cho đồ thị có hướng gồm ~N~ đỉnh, ~M~ cung (có trọng số là độ dài cung).

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

Input

• Dòng 1: ~N, M~ (~2 \le N \le 20.000; 0 \le M \le 100.000~).
• ~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 d \le 100.000~). (Các số cách nhau ít nhất 1 dấu cách)

Output

• Một số duy nhất là độ dài đường đi ngắn nhì, nếu không có thì ghi -1.

Sample Input 1

4 6
1 2 5
1 3 5
2 3 1
2 4 5
3 4 5
1 4 13

Sample Output 1

11

Giải thích: Ngắn nhất: 1 -> 2 -> 4 hoặc 1 -> 3 -> 4 độ dài 10. Ngắn nhì: 1 -> 2 -> 3 -> 4: độ dài 11

Sample Input 2

2 2
1 2 1
2 1 1

Sample Output 2

3

Giải thích: Ngắn nhất: 1 -> 2 độ dài 1. Ngắn nhì: 1 -> 2 -> 1 -> 2: độ dài 3

Subtasks