An muốn đi xe máy từ thành phố \(1\) đến thành phố N. Bản đồ gồm có N thành phố và M tuyến đường liên tỉnh một chiều nối giữa chúng, con đường thứ i có chiều dài \(w\).

Hãy giúp An tìm đường đi ngắn nhất từ thành phố \(1\) đến thành phố \(N\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và M (\(1 \le N \le 10^5, 0 \le M \le 2 \cdot 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le u, v \le N, 1 \le w \le 10^9\)) mô tả con đường một chiều từ u sang v có độ dài là \(w\).

Định dạng đầu ra

• Một số nguyên duy nhất là độ dài đường đi ngắn nhất. Nếu không thể đi tới, in ra \(-1\).

Ví dụ

Input:

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

Output:

8

Ràng buộc