Anh Bình làm nhân viên giao hàng nhanh cho một công ty chuyển phát lớn. Công ty có \(N\) kho hàng được đánh số từ \(1\) đến \(N\), trong đó kho \(1\) là kho trung tâm ở Hà Nội và kho \(N\) là kho đích ở thành phố Hồ Chí Minh. Hệ thống có \(M\) tuyến giao hàng giữa các kho, mỗi tuyến được phép đi từ kho \(u\) đến kho \(v\) với chi phí vận chuyển là \(w\) đồng.

Do các tuyến đều được xây dựng để phục vụ cho việc chuyển hàng theo hướng đi từ Bắc vào Nam hoặc từ các kho lớn đến các kho nhỏ hơn về phía sau, tập các tuyến đảm bảo không tạo thành vòng khép kín nào. Tất cả chi phí vận chuyển đều là số nguyên dương.

Anh Bình cần tìm một cách đi từ kho \(1\) đến kho \(N\) sao cho tổng chi phí vận chuyển là nhỏ nhất. Anh hỏi An: chi phí nhỏ nhất là bao nhiêu?

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

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 2 \cdot 10^5\), \(0 \le M \le 5 \cdot 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) mô tả một tuyến đi từ kho \(u\) đến kho \(v\) với chi phí \(w\) (\(1 \le w \le 10^9\)).
• Đảm bảo: luôn có ít nhất một cách đi từ kho \(1\) đến kho \(N\).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng chi phí nhỏ nhất để đi từ kho \(1\) đến kho \(N\).

Ví dụ

Input:

5 6
1 2 5
1 3 2
2 4 3
3 4 1
4 5 4
2 5 8

Output:

7

Giải thích: Đường đi \(1 \to 3 \to 4 \to 5\) có tổng chi phí \(2 + 1 + 4 = 7\), là nhỏ nhất.

Ràng buộc

• \(1 \le N \le 2 \cdot 10^5\)
• \(0 \le M \le 5 \cdot 10^5\)
• \(1 \le w \le 10^9\)
• Luôn có ít nhất một cách đi từ kho \(1\) đến kho \(N\).
• Hệ thống các tuyến đảm bảo không tạo vòng khép kín.