Phiếu giảm phí một chặng

Bối cảnh và bài toán

Một lộ trình vận chuyển có chi phí dương trên các cung. Doanh nghiệp có một phiếu giảm 50% chi phí của đúng một cung, làm tròn xuống.

Yêu cầu

Tính chi phí nhỏ nhất từ 1 tới n khi bắt buộc sử dụng phiếu trên đúng một cạnh.

Input

Dòng đầu n, m; tiếp theo m cạnh có hướng u, v, w.

Output

In chi phí nhỏ nhất.

Ràng buộc

• 2 <= n <= 10^5
• 1 <= m <= 2*10^5
• 1 <= w <= 10^9 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

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

Output

2

Giải thích. Trạng thái thứ hai ghi việc phiếu đã dùng hay chưa, nên mọi phương án hợp lệ đều được xét.

Ví dụ 2

Input

2 1
1 2 10

Output

5

Giải thích. Trạng thái thứ hai ghi việc phiếu đã dùng hay chưa, nên mọi phương án hợp lệ đều được xét.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Flight Discount. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.