Bạn là thị trưởng của vùng Berlyatov. Vùng này có ~ n ~ thị trấn và có ~ m ~ con đường nối liền chúng. Các thị trấn được đánh số thứ tự từ 1 đến ~ n ~. Con đường thứ ~ i ~ nối liền hai thị trấn ~ x_i ~ và ~ y_i ~ với chi phí di chuyển trên tuyến đường này là ~ w_i ~.

Có ~ k ~ tuyến đường được dùng để giao hàng ở Berlyatov, tuyến thứ ~ i ~ xuất phát từ thị trấn ~ u_i ~ và kết thúc ở thị trấn ~ v_i ~. Trên một tuyến đường có một người làm nhiệm vụ giao hàng và người đó luôn lựa chọn con đường có tổng chi phí di chuyển là nhỏ nhất.

Hãy chọn một con đường và thay đổi chi phí di chuyển thành 0 sao cho ~ ∑d(u_i,v_i) ~ là nhỏ nhất, trong đó ~ d(u_i,v_i) ~ là chi phí di chuyển trên tuyến đường từ ~ u_i ~ đến ~ v_i ~.

Dữ liệu vào

• Dòng đầu tiên ghi lần lượt ba số nguyên dương ~ n, m, k ~ tương ứng là số lượng thị trấn, số lượng con đường và số lượng tuyến đường giao hàng.
• ~ m ~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~ x_i,y_i,w_i (1≤x,y≤n;x≠y) ~ trong đó ~ w_i ~ là chi phí di chuyển trên con đường. Có thể có nhiều con đường nối liền hai thị trấn hoặc có một con đường một thị trấn với chính nó.
• ~k~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~ u_i, v_i ~ cho biết thông tin về một tuyến đường dùng để giao hàng.

Kết quả

• Ghi một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc

• ~ 2≤n≤1000 ~
• ~ n-1≤m≤min⁡(1000,n(n-1)/2) ~
• ~ 1≤k≤1000 ~
• ~ 1≤w_i≤1000 ~

Ví dụ:

Input 1

6 5 2
1 2 5
2 3 7
2 4 4
4 5 2
4 6 8
1 6
5 3 

Output 1

22 

Input 2

5 5 4
1 2 5
2 3 4
1 4 3
4 3 7
3 5 2
1 5
1 3
3 3
1 5 

Output 2

13