Công ty du lịch XYZ thường tổ chức các tuyến du lịch tham quan địa điểm được đánh số từ đến . Các địa điểm du lịch này được nối với nhau không những bởi một hệ thống giao thông đường bộ mà còn cả một hệ thống giao thông đường thuỷ. Có một đoàn khách du lịch muốn đến đặt một tour du lịch xuất phát từ địa điểm kết thúc ở địa điểm . Đoàn khách du lịch có hai người phụ trách đi lại cho đoàn: ông An phụ trách đi đường bộ còn ông Bình phụ trách đi đường thuỷ.
Để hành trình đem lại nhiều điều thú vị, đoàn khách quyết định ban ngày chỉ đi theo đường bộ còn ban đêm chỉ đi theo đường thuỷ từ một địa điểm này đến một địa điểm khác. Ông An được Công ty XYZ cung cấp cho bản đồ giao thông đường bộ, còn ông Bình được cung cấp bản đồ giao thông đường thuỷ để theo dõi hành trình của đoàn. Hướng dẫn viên du lịch Nguyễn Văn C... (vì lý do tế nhị ta không tiết lộ tên) được giao nhiệm vụ dẫn đường cho đoàn. Hành trình càng dài thì công ty càng có lợi và tất nhiên C càng thu được nhiều tiền thù lao. Thực hiện điều đó không phải là việc dễ dàng vì mỗi ngày C phải báo cáo về lộ trình của đoàn: đầu mỗi buổi sáng C báo cho ông An biết đoàn sẽ đi tới đâu, còn đầu mỗi buổi tối C báo cho ông Bình biết đoàn sẽ đi tới địa điểm nào. Do đó mỗi lần chọn tuyến đường di chuyển C phải chọn tuyến đường bộ (để báo cáo ông An) hoặc
tuyến đường thuỷ (để báo cáo ông Bình) sao cho độ dài đường đi ngắn nhất đến địa điểm đích phải giảm ngặt (nghĩa là nếu C chọn tuyến đường bộ/thuỷ đi từ đến thì trên bản đồ đường bộ/thuỷ độ dài đường đi ngắn nhất từ đến phải lớn hơn độ dài đường đi ngắn nhất từ đến ).
Yêu cầu: Giúp C tìm độ dài của hành trình dài nhất.
Dữ liệu vào:
Dòng đầu tiên chứa ba số nguyên theo thứ tự là số lượng điểm du lịch, điểm xuất phát và điểm kết thúc của hành trình ).
Tiếp đến là hai nhóm dòng mô tả bản đồ giao thông đường bộ và bản đồ giao thông đường thuỷ, mỗi nhóm có cấu trúc như sau:
Dòng đầu tiên chứa số nguyên là số lượng tuyến đường trong hệ thống ;
Mỗi dòng trong số dòng tiếp theo chứa ba số nguyên mô tả một tuyến đường (bộ/thuỷ) giữa hai địa điểm vd\ (1 ≤ u, v ≤ n; 1 ≤ d ≤ 10^6)$.
Các tuyến đường kể cả thuỷ lẫn bộ đều cho phép đi theo cả hai chiều. Dữ liệu đảm bảo luôn có cách đi từ một địa điểm bất kỳ đến bất kỳ địa điểm nào trong số các địa điểm còn lại theo hệ thống đường bộ cũng như theo hệ thống đường thuỷ. Đoàn khách du lịch khởi hành từ thành phố xuất phát vào buổi sáng.
Dữ liệu ra:
Ghi ra độ dài của hành trình dài nhất tìm được. Nếu C có cách dẫn đoàn khách đi không khi nào tới đích hãy ghi số .
