A. CROBOT - Chu trình

Giáo sư X chế tạo một Robot tham gia cuộc thi của câu lạc bộ CSP Robotics. Bài thi diễn ra trên sơ đồ giao thông gồm địa điểm và con đường một chiều nối các địa điểm đó. Các địa điểm được đánh số từ tới và các con đường đánh số từ tới . Con đường thứ cho phép robot đi từ địa điểm tới địa điểm và theo đặc thù thiết kế, robot của giáo sư X có thể đi qua con đường này trong thời gian là .

Trong bài thi, robot cần được đặt ở một địa điểm tùy chọn làm nơi xuất phát, sau đó phải thực hiện phép di chuyển qua đúng con đường, mỗi con đường có thể đi qua nhiều lần, để quay về nơi xuất phát. Hãy giúp giáo sư X tìm ra hành trình tiết kiệm thời gian nhất cho con robot của mình.

Dữ liệu vào:

• Dòng đầu chứa ba số nguyên dương ;
• dòng tiếp theo, dòng thứ chứa ba số nguyên dương .

Các số trên một dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra:

• Ghi ra một số nguyên duy nhất là thời gian ít nhất để thực hiện hành trình theo phương án tìm được. Nếu không tồn tại hành trình đáp ứng yêu cầu, ghi ra .

Ví dụ:

Dữ liệu vào:

6 8 11
1 2 1
2 3 1
3 4 2
4 5 10
4 6 1
5 5 8
5 2 10
6 3 1

Dữ liệu ra:

39

Dữ liệu vào:

2 2 3
1 2 1
2 1 1

Dữ liệu ra:

-1

Giải thích:

Ví dụ 1: Một trong những hành trình tối ưu là: