Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

* Các bạn HS chú ý: Khi nộp bài máy chấm chỉ chấm test 1 của ví dụ, sau khi kết thúc bài KT chúng tôi sẽ chấm lại 
với bộ test đầy đủ, vì vậy hãy test kỹ trước khi nộp bài mình.

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à Cij = Cji đồ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í dụ: Thành phố có 5 nút giao thông và 6 tuyến xe buýt:

Tuyến 1: 1-2 giá vé 10 đồng; Tuyến 2: 2-5 giá vé 10 đồng,

Tuyến 3: 1-4 giá vé 3 đồng; Tuyến 4: 3-4 giá vé 5 đồng,

Tuyến 5: 3-5 giá vé 3 đồng; Tuyến 6: 1-3 giá vé 20 đồng.

Đường đi 1->4->3->5 hết 11 đồng là í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ó.

Input

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

Output

• 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ó.

Example

Ví dụ 1


Ví dụ 2




INPUT


OUTPUT


INPUT


OUTPUT




5   6
1   2 10
2   5 10
1   4 3
3   4 5
3   5 3
1   3 20


3


5   5
1   2 10
2   5 10
1   4 3
4   3 5
3   5 3


6