Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Moony mới khai chương một trung tâm giải trí và nó đã thu hút được khá nhiều lượt khách đến trong tuần đầu mở cửa. Do mọi thứ mới đang trong giai đoạn khởi đầu nên Moony muốn sáng tạo thêm một số ý tưởng để làm tăng doanh thu của trung tâm giải trí.

Trung tâm giải trí của Moony gồm N khu vui chơi. Giữa hai khu vui chơi bất kì có nhiều nhất một đoạn đường nối hai chiều và hệ thống đoạn đường nối đảm bảo luôn có đường đi qua các đoạn đường nối giữa hai khu vui chơi bất kỳ. Moony gọi đó là tính liên thông của hệ thống đoạn đường nối. Dọc theo các đoạn đường nối, Moony bố trí các quán ăn, quầy lưu niệm,… và đó cũng là một nguồn thu đáng kể của trung tâm giải trí.

Quan sát các lượt khách thăm quan, Moony chợt nảy ra một ý tưởng thú vị để tăng doanh thu. Moony sẽ trang trí lại một số đoạn đường nối. Anh nghĩ rằng mọi người sẽ thích đi qua những đoạn đường nối được trang trí hơn. Chi phí trang trí cho mỗi đoạn đường nối là như nhau, và anh dự định tiết kiệm kinh phí trang trí hết mức có thể nhưng vẫn đảm bảo hệ thống các đoạn đường nối được trang trí là một hệ thống có tính liên thông. Cuối cùng, trong số những phương án khả thi, Moony sẽ chọn ra phương án mà tổng doanh thu từ các dịch vụ trên các đoạn đường nối là lớn nhất.

Một ý tưởng tuyệt vời! Nhưng Moony chợt nhận ra có những đoạn đường nối có phong cảnh rất đẹp. Anh đếm được có Q đoạn đường như vậy. Moony quyết định sẽ thêm một yếu tố nữa vào ý tưởng của anh: với từng đoạn đường nối có phong cảnh đẹp, phương án các đoạn đường được trang trí sẽ phải có đoạn đường nối ấy, rồi sau đó mới xét đến doanh thu tối đa.

Hãy giúp Moony tìm ra phương án có doanh thu lớn nhất với mỗi đoạn đường nối có phong cảnh đẹp.

Input

Dòng đầu tiên gồm 3 số nguyên N, M, Q (1 ≤ N ≤ 10⁵, N – 1 ≤ M ≤ min{N(N – 1)/2, 2.10⁵}, 1 ≤ Q ≤ M) lần lượt là số lượng khu vui chơi, số đoạn đường nối và số đoạn đường nối có phong cảnh đẹp.

M dòng tiếp theo, mỗi dòng gồm 3 số u, v, c (1 ≤ u, v ≤ N, u ≠ v, 1 ≤ c ≤ 10⁹) thể hiện đoạn đường nối giữa khu vui chơi u và v có doanh thu là c.

Q dòng tiếp theo, mỗi dòng gồm 2 số u, v (1 ≤ u, v ≤ N, u ≠ v) tương ứng với một phương án của đoạn đường có phong cảnh đẹp giữa hai khu vui chơi u và v. Dữ liệu đảm bảo tồn tại đoạn đường nối này trong M đoạn đường nối ở trên.

Output

In ra Q dòng, mỗi dòng là tổng chi phí lớn nhất đạt được với phương án tương ứng.

Example

Input:
4 5 3
1 2 4
1 3 3
2 4 2
1 4 4
4 3 2
3 4
1 2
2 4
Output:
10
11
9