Bản đồ thành phố của Bình có \(N\) địa điểm đặc biệt. Do khu vực trung tâm mật độ xây dựng cực kỳ dày đặc nên giữa hầu hết tất cả các cặp địa điểm đều có tuyến đường kết nối trực tiếp.

Hãy tìm độ dài đường đi ngắn nhất từ địa điểm \(1\) đến địa điểm \(N\).

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

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 5000\), \(0 \le M \le 10^7\)).
• \(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ả tuyến đường hai chiều giữa \(u\) và \(v\). Có thể có nhiều đường nối giữa cùng một cặp địa điểm, hãy lấy khoảng cách nhỏ nhất.

Định dạng đầu ra

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

Ràng buộc

Ví dụ

Input:

3 3
1 2 5
2 3 10
1 3 20

Output:

15