Cho một đồ thị có hướng gồm N đỉnh và M cung, mỗi cung có trọng số dương.

Hãy tìm độ dài của đường đi ngắn thứ hai từ đỉnh 1 đến đỉnh N.

Đường đi ngắn thứ hai là đường đi có độ dài nhỏ nhất lớn hơn độ dài của đường đi ngắn nhất. Đường đi có thể đi qua một đỉnh hoặc một cung nhiều lần.

Nếu không tồn tại đường đi ngắn thứ hai, hãy in ra -1.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên N, M (2 ≤ N ≤ 20 000, 0 ≤ M ≤ 100 000).
• M dòng tiếp theo, mỗi dòng chứa ba số nguyên a, b, d, cho biết có một cung một chiều từ a đến b với trọng số d (1 ≤ d ≤ 100000).

Dữ liệu ra

• Một số nguyên duy nhất là độ dài của đường đi ngắn thứ hai từ đỉnh 1 đến đỉnh N.

Nếu không tồn tại đường đi ngắn thứ hai thì in ra -1.

INPUT

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

OUTPUT

11

Đường đi ngắn nhất là 1 → 2 → 4 hoặc 1 → 3 → 4, đều có độ dài 10.

Đường đi ngắn thứ hai là 1 → 2 → 3 → 4, có độ dài 11.

INPUT

2 2
1 2 1
2 1 1

OUTPUT

3

Đường đi ngắn nhất là 1 → 2, có độ dài 1.

Đường đi ngắn thứ hai là 1 → 2 → 1 → 2, có độ dài 3.