Mô tả bài toán: Tìm đường bay rẻ nhất với phiếu giảm giá

Nhiệm vụ của bạn là tìm đường bay có giá rẻ nhất từ Syrjälä đến Metsälä. Bạn có một phiếu giảm giá, cho phép bạn giảm một nửa giá (làm tròn xuống) của một chuyến bay bất kỳ trên đường đi. Tuy nhiên, bạn chỉ có thể sử dụng phiếu giảm giá một lần.

Input:

• Dòng đầu tiên chứa hai số nguyên n và m: số lượng thành phố và số lượng chuyến bay.
• Sau đó, có m dòng, mỗi dòng chứa ba số nguyên a, b, và c:
  • ~a~: thành phố xuất phát của chuyến bay.
  • ~b~: thành phố đích của chuyến bay.
  • ~c~: giá của chuyến bay từ ~a~ đến ~b~.
• Các chuyến bay là một chiều.

Output:

• In ra một số nguyên: giá rẻ nhất của đường bay từ Syrjälä (thành phố 1) đến Metsälä (thành phố ~n~).

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