Chuyến phiêu lưu đến Metsälä

Syrjälä, một thành phố sầm uất, đang tổ chức lễ hội lớn nhất trong năm. Tuy nhiên, bạn lại đang ở Metsälä, một vùng đất xa xôi, và cần tìm cách quay về tham dự sự kiện này với chi phí thấp nhất.

Bạn có một tấm "Thẻ Vàng Ưu Đãi", cho phép giảm giá một lần duy nhất trên một chuyến bay bất kỳ. Khi sử dụng thẻ này, giá vé của chuyến bay đó sẽ giảm một nửa (làm tròn xuống số nguyên).

Hãy tìm lộ trình rẻ nhất để quay về Syrjälä từ Metsälä, tận dụng tối đa tấm thẻ ưu đãi của bạn!

Input

Dữ liệu được nhập từ bàn phím với định dạng như sau:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((2 \leq n \leq 10^5, 1 \leq m \leq 2 \cdot 10^5)\) --- số lượng thành phố và chuyến bay.
• Thành phố số 1 là Syrjälä (điểm đến).
• Thành phố số n là Metsälä (điểm xuất phát).
• Mỗi trong số \(m\) dòng tiếp theo chứa ba số nguyên \(a\), \(b\) và \(c\) \((1 \leq a, b \leq n, 1 \leq c \leq 10^9)\), mô tả một chuyến bay một chiều từ thành phố \(a\) đến thành phố \(b\) với giá vé \(c\).
• Luôn luôn có ít nhất một lộ trình từ Metsälä \((n)\) đến Syrjälä \((1)\).

Output

In một số nguyên duy nhất --- giá của hành trình rẻ nhất có thể đạt được khi sử dụng tối ưu "Thẻ Vàng Ưu Đãi".

Example

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

2