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

Khi bạn sử dụng phiếu giảm giá cho một chuyến bay có giá x, giá mới của chuyến bay sẽ là: ⌊x/2⌋ (tức là làm tròn xuống thành số nguyên).

Input:

Dòng đầu tiên chứa hai số nguyên n và m — lần lượt là số thành phố và số chuyến bay.

Các thành phố được đánh số từ 1, 2, ..., n.

Thành phố 1 là Syrjälä và thành phố n là Metsälä.

Sau đó có m dòng, mỗi dòng gồm ba số nguyên a, b, c:

a = thành phố xuất phát

b = thành phố đích

c = giá vé chuyến bay

Các chuyến bay chỉ đi một chiều.

Đảm bảo rằng luôn tồn tại ít nhất một đường đi từ Syrjälä đến Metsälä.

Output:

In ra một số nguyên duy nhất: giá rẻ nhất có thể đạt được để đi từ Syrjälä đến Metsälä.

Ràng buộc:

~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~

Ví dụ :

Input:

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

Output:

2