Chuyến Bay Giảm Giá

Có $n$ thành phố và $m$ chuyến bay một chiều. Bạn có một phiếu giảm giá dùng được đúng một lần, làm giảm giá chuyến bay đó xuống còn $\lfloor c/2\rfloor$. Tìm chi phí nhỏ nhất để đi từ thành phố $1$ đến thành phố $n$.

Dữ liệu vào

• Dòng 1: hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $a$, $b$, $c$ — chuyến bay từ $a$ đến $b$ với giá $c$.

Dữ liệu ra

In chi phí nhỏ nhất để đến thành phố $n$.

Ràng buộc

• $2\le n\le {10}^5$
• $1\le m\le 2\times {10}^5$
• $1\le c\le {10}^9$

Ví dụ