Đất nước đang trong công cuộc kiến thiết hạ tầng giao thông. Có hai loại phương tiện được sử dụng nhiều nhất cần được quan tâm, đó là ô tô và máy bay. Cân bằng chi phí giữa xây dựng đường bộ và sân bay là một bài toán nan giải.
Có thành phố trong đất nước . Chính phủ đã đề xuất đường bộ, con đường thứ sẽ nối giữa thành phố và , có chi phí xây dựng là . Để đảm bảo tính liên thông trong quốc gia cũng như quốc tế, chính phủ yêu cầu mỗi thành phố, hoặc phải xây dựng một sân bay trong thành phố, hoặc phải có thể di chuyển đến một thành phố có sân bay qua một hoặc nhiều con đường bộ.
Việc xây dựng sân bay được giải quyết bởi các nhà thầu. Mỗi nhà thầu có một khả năng xây dựng cũng như chi phí xây dựng sân bay khác nhau. Cụ thể, trong tổng cộng nhà thầu, nhà thầu thứ sẽ có thể xây tối đa sân bay, mỗi sân bay có chi phí xây dựng .
Nhiệm vụ của bạn là, với mỗi nhà thầu, xác định chi phí xây dựng đường bộ và sân bay nhỏ nhất để thỏa mãn yêu cầu của chính phủ.
Dữ liệu vào:
Dòng đầu tiên gồm ba số .
dòng tiếp theo, mỗi dòng gồm ba số thể hiện một tuyến đường bộ.
dòng tiếp theo, mỗi dòng gồm hai số và thể hiện thông tin của một nhà thầu.
Lưu ý: Đối với các bạn sử dụng ngôn ngữ C++, lượng dữ liệu nhập vào có thể rất lớn, các bạn nên sử dụng các phương pháp nhập nhanh (printf, getchar,…)
Dữ liệu ra:
In ra dòng, mỗi dòng gồm một số là chi phí xây dựng nhỏ nhất khi xét nhà thầu tương ứng. Nếu không thể thỏa mãn yêu cầu chính phủ, in .
Giới hạn:
;
;
Trong số test có .
Trong số test tiếp theo có và luôn có cách đi giữa hai thành phố bất kì sử dụng đường bộ.
Ví dụ
Dữ liệu vào:
4 2 3
2 4 9
3 4 9
7 4
10 3
1 1
Dữ liệu ra:
28
38
-1
Giải thích:
Nhà thầu : Xây sân bay, tổng chi phí là .
Nhà thầu : Xây đường bộ và sân bay ở và , tổng chi phí là .
Nhà thầu : Không thể thỏa mãn yêu cầu chỉ với sân bay.
