Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

YB_KT2B3 - Dạo phố

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


Được gửi lên bởi:Vương Trung Hiếu Nghĩa
Ngày:2014-08-14
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP C++ 4.3.2 CPP PAS-GPC PAS-FPC
Nguồn bài:HSG cấp trường chuyên YÊN BÁI

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.