Bessie chuyển tới trang trại nhỏ và đôi khi về thăm một bạn thân nhất. Thích phong cảnh nên không muốn tới nhà cũ quá nhanh, chọn đường ngắn thứ hai thay vì ngắn nhất. Cô biết đường đó tồn tại.

Có $R$ đường hai chiều ($1 \le R \le 100,000$), mỗi nối hai trong $N$ giao lộ ($1 \le N \le 5000$), đánh số $1..N$. Bắt đầu ở1, bạn và đích ở $N$.

Đường thứ hai có thể chung đường với bất kỳ ngắn nhất và quay lại, dùng đường hay giao lộ nhiều lần. Là ngắn nhất trong những đường dài hơn ngắn nhất. Nếu có nhiều ngắn nhất, nó dài hơn chúng nhưng không dài hơn đường nào khác.

Dữ liệu vào

Dòng 1: hai số nguyên cách nhau dấu cách, $N$ và $R$.

Các dòng $2..R+1$: ba số nguyên cách nhau dấu cách $A$, $B$, $D$, đường giữa $A$ và $B$ dài $D$ ($1 \le D \le 5000$).

Dữ liệu ra

Dòng 1: độ dài đường ngắn thứ hai từ1 tới $N$.

Ví dụ

Dữ liệu vào 1

4 4
1 2 100
2 4 200
2 3 250
3 4 100

Dữ liệu ra 1

450

Ghi chú

Gợi ý

Hai tuyến: $1 \to 2 \to 4$ (dài $100+200=300$) và $1 \to 2 \to 3 \to 4$ (dài $100+250+100=450$).