Con đường tơ lụa bắt đầu từ Phúc Châu, Hàng Châu, Bắc Kinh (Trung Quốc) qua Mông Cổ, Ấn Độ, Afghanistan, Kazakhstan, Iran, Iraq, Thổ Nhĩ Kỳ, Hy Lạp, xung quanh vùng Địa Trung Hải và đến tận châu Âu. Con đường cũng đi đến cả Hàn Quốc, Nhật Bản.
Mạng lưới giao thông của hệ thống đường này bao gồm trạm dừng chân cho ngựa và khách buôn bán (các trạm đánh số từ đến ). Giữa một số trạm có các con đường hiểm trở hai chiều (thủy hoặc bộ) nối trực tiếp và tùy theo địa hình, thời gian đi hết mỗi con đường này là khác nhau.
Nữ hoàng Ai Cập Cleopatra rất thích diện đồ tơ luạ ở Bắc Kinh và luôn lập các đoàn thương nhân đến Bắc Kinh để tìm mua loại tơ lụa nổi tiếng này. Đoàn thương nhân của nữ hoàng luôn xuất phát từ trạm dừng chân số và đích đến là trạm thông qua các đường nối khác nhau của con đường tơ lụa. Để đảm bào sức khỏe cho một cuộc hành trình dài các thương nhân cần phải chọn hành trình sao cho thời gian đi giữa hai trạm dừng chân càng ngắn càng tốt.
Bạn hãy giúp họ tìm con đường đi từ đến sao cho thời gian đi dài nhất giữa hai trạm dừng chân liên tiếp là ngắn nhất.
Dữ liệu vào:
Dòng đầu tiên ghi là số trạm và số tuyến đường ;
dòng tiếp theo mỗi dòng ghi ba số nguyên thể hiện có một đường nối trực tiếp giữa và có thời gian đi là .
Dữ liệu ra:
Một số nguyên duy nhất là thời gian của con đường đi lâu nhất trên hành trình.
