Trong thành phố Trùng Khánh có trạm xe, con đường hai chiều nối một số trạm với nhau. Giữa hai trạm bất kỳ có tối đa một con đường nối trực tiếp. Từ bất kỳ trạm nào cũng có thể đi qua một hoặc nhiều con đường để đến các trạm khác, nhưng các đường đi khác nhau có thể tốn thời gian khác nhau. Thời gian tốn trên một lộ trình bằng tổng thời gian của tất cả các con đường trên lộ trình đó.
Nhà của Jiajia ở trạm số , cậu ấy có 5 người thân lần lượt sống ở các trạm . Năm mới đến, cậu ấy cần xuất phát từ nhà mình, đến thăm từng người thân (thứ tự tùy ý), để gửi lời chúc mừng năm mới đến họ. Hỏi phải đi như thế nào để tốn ít thời gian nhất?
Dữ liệu:
Dòng đầu tiên: là số lượng trạm xe và số lượng con đường.
Dòng thứ hai: là số hiệu trạm của 5 người thân.
dòng tiếp theo, mỗi dòng ba số nguyên , là số hiệu hai trạm được nối bởi con đường và thời gian đi qua nó.
Kết quả:
Xuất ra duy nhất một dòng chứa một số nguyên , là tổng thời gian ít nhất.
