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

Giáo sư X cảm thấy mệt mỏi với công việc giảng dạy và nghiên cứu nên ông quyết định vác xe đi dạo quanh các con đường trong thành phố để thay đổi không khí. Có n địa điểm đánh số từ 1 tới n và m con đường một chiều đánh số từ 1 tới m. Con đường thứ i cho phép đi từ địa điểm u_i tới địa điểm v_i và có độ dài w_i. Hệ thống đường cho phép đi lại giữa hai địa điểm bất kỳ.

Giáo sư X xuất phát từ trường nằm tại địa điểm 1. Ông muốn đi qua tất cả m con đường rồi sau đó quay trở về trường. Ông có thể đi qua một con đường nhiều lần nhưng buộc phải đi theo chiều đã định của những con đường, bởi nếu đi ngược chiều thì ông sẽ được hưởng vài giờ nghỉ bất đắc dĩ tại trụ sở cảnh sát giao thông.

Yêu cầu: Tìm hành trình ngắn nhất cho giáo sư X thỏa mãn yêu cầu trên.

Input

• Dòng 1 chứa hai số nguyên dương n <= 10^3, m <= 10^4
• m dòng tiếp theo, dòng thứ  chứa ba số nguyên dương  u, v, w (w <= 10^6)

Output

• một số nguyên duy nhất là độ dài hành trình tìm được.

Example

DCPP.INP


DCPP.OUT


 




6 9
1 4 4
2 4 2
3 1 2
3 2 6
3 4 1
4 5 2
4 6 3
5 3 3
6 3 1


28


 
Hành trình cần tìm là
1->4->6->3->2->4->5->3->4->6->3->1