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\).

Ràng buộc

Ví dụ

Input:

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

Output:

8