Giảm giá chuyến bay

Trong một buổi phỏng vấn, FullHouse Dev được đưa ra một bài toán thú vị về việc tối ưu chi phí chuyến bay. Họ được yêu cầu tìm ra tuyến bay có giá rẻ nhất từ Syrjälä đến Metsälä, với một phiếu giảm giá đặc biệt.

Bài toán

Nhiệm vụ của bạn là tìm tuyến bay có giá thấp nhất từ Syrjälä đến Metsälä. Bạn có một phiếu giảm giá, cho phép giảm một nửa giá vé của bất kỳ chuyến bay nào trong tuyến đường. Tuy nhiên, bạn chỉ được sử dụng phiếu giảm giá một lần duy nhất. Khi sử dụng phiếu giảm giá cho một chuyến bay có giá \(x\), giá của nó sẽ trở thành \(\lfloor x/2 \rfloor\) (được làm tròn xuống thành số nguyên).

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng thành phố và số lượng đường bay. Các thành phố được đánh số từ \(1,2,\ldots,n\). Thành phố 1 là Syrjälä, và thành phố \(n\) là Metsälä.
• \(m\) dòng tiếp theo mô tả các chuyến bay. Mỗi dòng có ba số nguyên \(a\), \(b\), và \(c\): chuyến bay bắt đầu từ thành phố \(a\), kết thúc tại thành phố \(b\), và có giá \(c\). Mỗi chuyến bay chỉ một chiều. Bạn có thể giả định rằng luôn có thể đi từ Syrjälä đến Metsälä.

OUTPUT FORMAT:

• In ra một số nguyên: giá của tuyến đường rẻ nhất từ Syrjälä đến Metsälä.

Ràng buộc:

• \(2 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)
• \(1 \leq c \leq 10^9\)

Ví dụ

INPUT

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

OUTPUT

2

Giải thích

Tuyến đường tối ưu là đi từ thành phố 1 đến thành phố 2 (giá 3), sau đó từ thành phố 2 đến thành phố 3 (giá 1). Sử dụng phiếu giảm giá cho chuyến bay đầu tiên sẽ giảm giá từ 3 xuống 1. Vì vậy, tổng chi phí là 1 + 1 = 2.