Cho đồ thị có hướng có trọng số ~N~ đỉnh ~M~ cung. Bạn hãy tìm độ dài đường đi ngắn thứ 2 từ 1 đến ~N~.

Yêu cầu: Tìm độ dài đường đi ngắn thứ 2 từ đỉnh 1 đến đỉnh ~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ố ~a, b, d~ tương ứng là có đường đi 1 chiều từ ~a~ đến ~b~ độ dài ~d~ (~1 \le d \le 10.000~).

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