(vexe.*)

An là học sinh sống ở thành phố Hà Nội, hàng ngày em phải đi từ nhà tới trường bằng xe buýt. Thành phố có \(n\) nút giao thông được đánh số từ 1 đến \(n\) và \(m\) tuyến xe buýt hai chiều. Mỗi tuyến giao thông \((i,\ j)\) có không quá một tuyến xe buýt hai chiều, nếu có thì để đi từ nút \(i\) đến nút \(j\) (hoặc từ nút \(j\) đến nút \(i\)) với giá vé là \(t_{ij}\ = \ t_{ji}\) đồng. Nhà của An nằm ở nút giao thông \(1\) còn trường học lại ở nút giao thông \(n\).

Nhân kỷ niệm 110 năm thành lập trường An có nhận được một vé đi xe buýt miễn phí. Vé có thể dùng để đi xe buýt miễn phí một lần trên một tuyến bất kỳ. Với vé xe miễn phí này An muốn biết chi phí ít nhất để đi từ nhà đến trường là bao nhiêu?

Dữ liệu vào:

+ Dòng đầu tiên ghi hai số nguyên dương \(n\) và \(m\) \((3 \leq n \leq 100)\)

+ \(m\) dòng tiếp theo, mỗi dòng gồm 3 số nguyên \(i,\ j,\ t_{ij}(1 \leq i,j \leq n,\ 0 < t_{ij} \leq 30000)\) mô tả có tuyến xe buýt \((i,j)\) đi hết \(t_{ij}\) đồng.

Dữ liệu đảm bảo có đường đi từ 1 đến \(n\).

Kết quả:

+ Một số duy nhất là chi phí ít nhất để đi từ nhà đến trường với vé xe miễn phí mà An có.

Ví dụ: