An được thầy giáo thưởng cho một phiếu giảm giá 50% khi đi du lịch bằng xe bus. Ở đất nước của An có tất cả ~n~ thành phố và ~m~ tuyến xe bus một chiều nối giữa hai thành phố bất kì. Xuất phát từ thành phố ~1~, An mong muốn được tham quan thành phố ~n~ xinh đẹp. Với phiếu giảm giá được tặng, An quyết định sẽ đến thăm thành phố ~n~ và sử dụng phiếu giảm giá để giảm tối thiểu chi phí đi lại. Biết rằng, phiếu giảm giá chỉ có thể sử dụng duy nhất một lần ở bất kỳ tuyến xe bus nào. Giả sử, An áp dụng phiếu giảm giá cho tuyến xe bus có giá là ~x~, thì giá mà An phải trả sẽ là ~\lfloor x/2 \rfloor~ (làm tròn xuống thành một số nguyên).

Yêu cầu

Hãy tính tổng số tiền tối thiểu mà An phải trả khi đi du lịch đến thành phố ~n~.

Input

Đọc từ tệp TRAVEL.INP:

• Dòng đầu tiên chứa hai số ~n~ và ~m~ tương ứng là số lượng thành phố và số tuyến xe bus nối giữa hai thành phố. Các thành phố được đánh số từ ~1, 2, \ldots, n~.
• ~m~ dòng sau, mỗi dòng gồm ba số nguyên ~a~, ~b~ và ~c~ tương ứng là tuyến xe bus từ thành phố ~a~ đến thành phố ~b~ sẽ có giá là ~c~ (~a, b \le n~ và ~1 \le c \le 10^9~).

Lưu ý: Mỗi tuyến xe bus đều là một chiều và luôn tồn tại cách di chuyển từ nơi An sống đến thành phố ~n~.

Output

Ghi vào tệp TRAVEL.OUT số nguyên dương duy nhất là chi phí tối thiểu cho An khi đi du lịch đến thành phố ~n~.

Ví dụ

Input

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

Output

2

Giải thích: An sẽ đi theo lộ trình: ~1 \to 2 \to 3~. An áp dụng phiếu giảm giá ở tuyến đường ~1 \to 2~ để có chi phí bằng ~1~, đi từ ~2 \to 3~ có chi phí là ~1~. Tổng chi phí An phải trả là ~1 + 1 = 2~.

Giới hạn

• Có 50% số test của bài thỏa mãn ~1 < n, m \le 10^2~.
• Có 30% số test tiếp theo của bài thỏa mãn ~10^2 < n, m \le 10^3~.
• Có 20% số test còn lại của bài thỏa mãn ~10^3 < n, m \le 10^5~.