Phiếu Giảm Giá Một Chặng

Có $n$ thành phố được đánh số từ $1$ đến $n$ và $m$ chuyến bay một chiều. Chuyến bay từ $a$ tới $b$ có giá vé $c$.

Bạn cần đi từ thành phố $1$ tới thành phố $n$ và có một phiếu giảm giá. Phiếu phải được dùng cho đúng một chuyến bay trên hành trình. Nếu chuyến đó có giá $c$, số tiền phải trả cho nó là $\lfloor c/2\rfloor$; giá của mọi chuyến còn lại giữ nguyên.

Hãy tìm tổng tiền nhỏ nhất cần trả. Dữ liệu bảo đảm luôn tồn tại ít nhất một hành trình từ $1$ tới $n$.

Input

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Mỗi trong $m$ dòng tiếp theo chứa ba số nguyên $a,b,c$, biểu thị một chuyến bay một chiều từ $a$ tới $b$ có giá $c$.

Output

• In tổng chi phí nhỏ nhất của một hành trình từ $1$ tới $n$ sau khi dùng phiếu đúng một lần.

Constraints

• $2\le n\le 10^5$.
• $1\le m\le 2\cdot 10^5$.
• $1\le a,b\le n$.
• $1\le c\le 10^9$.
• Cạnh tự khuyên và nhiều chuyến bay cùng đầu mút đều được phép.
• Luôn có đường đi có hướng từ $1$ tới $n$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 40,m\le 100$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4 5
1 2 8
2 4 7
1 3 5
3 4 10
2 3 1

10

3 3
1 2 9
2 3 1
1 3 11

5