Nhiệm vụ của bạn là tìm một lộ trình bay rẻ nhất từ Syrjälä đến Metsälä. Bạn có một phiếu khuyến mãi, sử dụng nó có thể giảm một nửa giá của bất kỳ chuyến bay nào trong suốt lộ trình. Tuy nhiên, bạn chỉ có thể sử dụng phiếu đó một lần.

Input

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

Output

• In một số nguyên: giá của lộ trình rẻ nhất từ Syrjälä đến Metsälä.
• Khi bạn sử dụng phiếu khuyến mãi cho một chuyến bay mà giá tiền của nó là \(x\), giá tiền của nó trở thành \(\lfloor x/2 \rfloor\) (làm tròn xuống một số nguyê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\)

Example

Sample input

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

Sample output

2