An sống ở thành phố XYZ, hàng ngày anh phải đi làm từ nhà tới cơ quan bằng xe buýt. Thành phố XYZ 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 cặp nút 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à c_ij=c_ji đồng. Vị trí nhà An nằm ở nút giao thông 1 còn cơ quan nằm ở nút giao thông n. Để lựa chọn đường đi từ nhà đến cơ quan An luôn chọn theo đường đi với chi phí ít nhất.

Vừa qua An 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 cơ quan là bao nhiêu.

Với ví dụ trên, đường đi 1 -> 3 -> 5 có sử dụng vé xe miễn phí (tại tuyến 1-3) hết 3 đồng là ít nhất.

Yêu cầu: Cho biết các tuyến xe buýt và giá vé tương ứng. Hãy tìm chi phí ít nhất để đi từ nhà (nút giao thông 1) đến cơ quan (nút giao thông n) với vé xe miễn phí mà An có.

Dữ liệu vào 

• Dòng đầu tiên ghi hai số nguyên dương n và m (3<=n<=5000)
• m dòng sau, mỗi dòng 3 số nguyên i, j, c_ij (1 <= i, j <=n, 0<=c_ij <=30000) mô tả có tuyến xe buýt  i -> j hết  c_ij  đồng.

Hai số liên tiếp trên một dòng cách nhau một dấu cách. Dữ liệu bảo đảm luôn có đường đi từ  1 đến n.

Kết quả

Ghi ra một số duy nhất là chi phí ít nhất để đi từ nhà (nút giao thông 1) đến cơ quan (nút giao thông n) với vé xe miễn phí mà An có.