Có \(n\) thành phố và có \(m\) chuyến bay đi qua lại giữa các thành phố. Hạo có 1 mã giảm giá, khi sử dụng mã này thì sẽ được giảm giá 1 chuyến bay đi phân nửa giá tiền (x đồng sẽ thành x/2 đồng - làm tròn xuống). Hãy giúp Hạo lên lịch trình bay từ thành phố \(1\) đến thành phố \(N\) với chi phí ít nhất.

Input

• Dòng đầu tiên gồm \(2\) số nguyên \(n,m\).
• \(m\) dòng tiếp theo, mỗi dùng gồm \(3\) số nguyên \(u,v,c\), thể hiện chuyến bay từ thành phố \(u\) đến thành phố \(v\) có chi phí là \(c\).

Output

• Chi phí thấp nhất tìm được.

Điều kiện

• \(1 \le n \le 10^5\)
• \(1 \le m \le 2 \times 10^5\)
• \(1 \le u,v \le n\)
• \(1 \le c \le 10^9\)

Sample Input 1

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

Sample Output 1

2