Thành phố ByteLand là một trung tâm tin học nổi tiếng trên thế giới. Đây cũng là nơi sinh sống và lập nghiệp của rất nhiều lập trình viên từ các nước khác nhau.
Mới đây, ở ByteLand đã xây dựng tượng đài "Người lập trình vô danh" để ghi nhận công lao của rất nhiều lập trình viên tuy không nổi tiếng nhưng lại cung cấp rất nhiều chương trình nhỏ tiện ích và miễn phí trên mạng internet. Đây cũng là một công trình kiến trúc đẹp và được thế giới xếp vào trong kỳ quan hiện đại.
Với mục đích giới thiệu kỳ quan này đến với mọi khách du lịch khi đến ByteLand, chính quyền thành phố ban hành qui định Tất cả các xe taxi khi chở khách du lịch đều phải đi qua tượng đài Người lập trình vô danh trên mỗi hành trình chở khách.
Mạng lưới giao thông của ByteLand bao gồm nút giao thông (đánh số từ được nối với nhau bởi con đường hai chiều. Mỗi con đường nối trực tiếp giữa hai nút giao thông nào đó. Có thể có nhiều con đường trực tiếp nối hai nút giao thông. Mỗi một con đường có một độ dài xác định. Tượng đài Người lập trình vô danh được xây dựng ở nút số .
Có khách du lịch, người khách thứ có nhu cầu di chuyển từ nút giao thông đến nút giao thông bằng taxi. Hãy tính xem mỗi người phải trả ít nhất là bao nhiêu BCoin (đơn vị tiền tệ ở ByteLand) biết rằng giá taxi thống nhất là BCoin cho đơn vị độ dài.
Dữ liệu:
Dòng đầu tiên ghi ba số nguyên ;
dòng tiếp theo, dòng thứ ghi ba số nguyên thể hiện có một con đường hai chiều nối hai nút giao thông và có độ dài ;
dòng cuối cùng, dòng thứ ghi hai số nguyên và thể hiện rằng người khách du lịch thứ muốn đi từ nút giao thông đến nút giao thông .
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu trống.
Kết quả:
Ghi ra dòng, dòng thứ ghi số nguyên là số tiền ít nhất mà người du lịch thứ phải trả cho chuyến taxi của mình.
