Ở một thành phố nọ, mật độ dân số cao, đường xá thì chật hẹp, vấn đề giao thông và môi trường trở nên khó khăn với nhiều người dân. Nhằm khuyến khích người dân hạn chế dùng phương tiện cá nhân, chính quyền thành phố phát triển hệ thống giao thông công cộng là xe bus. Có n trạm xe bus đánh dấu từ 1 đến n. Có m tuyến đường, tuyến thứ i nối trực tiếp hai trạm ui và vi với thời gian di chuyển ti, chú ý ui nối vi không có nghĩa vi nối ui và không lặp lại (1≤ m < n2, i: 1 .. m, 1≤ ui , vi ≤ n).
Sau nhiều năm sử dụng xe bus, đến nay người dân vẫn cảm thấy không thoải mái. Ví dụ họ muốn biết, nếu xuất phát từ một trạm s đến một trạm f thì có đi xe bus được không (có thể đi gián tiếp), nếu đi được thì tìm số lượng tuyến ít nhất để số lần chuyển xe ít nhất và thời gian ít nhất, cho thời gian chuyển tuyến bằng không. Có p yêu cầu như thế, yêu cầu thứ j có trạm xuất phát sj và trạm đích fj (j: 1 .. p, 1≤ sj , fj ≤ n). Bạn có thể giúp chính quyền thành phố giải quyết bài toán.
Yêu cầu chung: Cho n, m, p, ui, vi, ti, sj, fj (2≤ n ≤103, 1≤ p ≤107, 1≤ ti ≤103, i: 1 .. m, j: 1 .. p). Hãy tìm số lượng tuyến ít nhất và thời gian nhất ít nhất cho mỗi yêu cầu trong p yêu cầu. Lưu ý: số lượng tuyến ít nhất và thời gian ít nhất là hai ý độc lập. Thời gian chạy chương trình trong vòng 1 giây.
Dữ liệu: Vào từ file văn bản Bus.inp:
• Dòng đầu chứa 3 số nguyên n, m, p
• m dòng tiếp theo, mỗi dòng chứa ui, vi, ti.
• p dòng tiếp theo, mỗi dòng chứa cặp sj, fj.
• Các số trên cùng dòng cách nhau ít nhất một khoảng trắng.
Kết quả: Đưa ra file văn bản Bus.out:
• Ghi p dòng đầu tiên theo thứ tự p yêu cầu đã cho, mỗi dòng nếu tìm thấy thì ghi số tuyến ít nhất và thời gian ít nhất, ngược lại thì dòng đó ghi -1.
• Ghi thêm dòng cuối cùng chứa tổng số tuyến ít nhất và tổng thời gian ít nhất của p yêu cầu, ngoại trừ yêu cầu không tìm thấy.
• Các số trên cùng 1 dòng cách nhau 1 khoảng trắng.
Ví dụ:
Bus.inp Bus.out
5 6 2 1 2
1 2 1 3 13
2 3 1 4 15
1 3 4
3 4 5
4 5 6
5 1 7
1 3
1 5