Đề bài

Có ~ n ~ thành phố, được đánh từ ~ 1 ~ đến ~ n ~, chúng được kết nối bởi một số đường một chiều. Mỗi đường thứ ~ i ~ có một chi phí ~ c(i) ~, điều đó có nghĩa là chi phí để vượt qua cạnh thứ ~ i ~ là ~ c(i) ~ thời gian.

Bây giờ yêu cầu từ ~ 1 ~ đến ~ n ~. Hỏi thời gian tối thiểu cần thiết là bao nhiêu.

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

1. Hai số nguyên trong dòng đầu tiên ~ n ~ và ~ m ~ (biết số lượng thành phố và đường bộ).
2. Tiếp theo ~ m ~ dòng, mỗi dòng gồm 3 số nguyên ~ u, v, c ~: nghĩa là có một đường từ ~ u ~ đến ~ v ~ tốn thời gian ~ c ~.

Định dạng đầu ra

1. Một số nguyên duy nhất: thời gian tối thiểu cần thiết từ ~ 1 ~ đến ~ n ~. Nếu không có đường đi, in ra -1.

Ví dụ

Input

4 5
1 2 20
1 3 10
3 2 5
2 4 7
3 4 15

Output

22

Giải thích:

• Đường đi tối ưu: ~ 1 \to 3 \to 2 \to 4 ~.
• Tổng chi phí thời gian là ~ 10 + 5 + 7 = 22 ~.