Giảm chi phí giao hàng

Cho một đồ thị vô hướng liên thông gồm $n$ đỉnh và $m$ cạnh. Cạnh thứ $i$ nối hai đỉnh $x_i$ và $y_i$ với trọng số $w_i$ (chi phí đi qua cạnh đó).

Có $k$ tuyến giao hàng. Tuyến thứ $i$ đi từ đỉnh $a_i$ đến đỉnh $b_i$. Người đưa hàng luôn chọn con đường có tổng chi phí nhỏ nhất giữa $a_i$ và $b_i$. Cho phép $a_i=b_i$ (khi đó chi phí là $0$), và các tuyến có thể trùng nhau (mỗi tuyến vẫn được đếm riêng).

Bạn được phép chọn nhiều nhất một cạnh và đặt chi phí của cạnh đó bằng $0$ (hoặc không chọn cạnh nào). Gọi $d(u,v)$ là chi phí nhỏ nhất giữa hai đỉnh $u$ và $v$ sau khi thay đổi. Hãy tìm giá trị nhỏ nhất có thể của tổng

$$\sum _{i=1}^{k}d(a_i,b_i).$$

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $x_i$, $y_i$, $w_i$ mô tả một cạnh.
• $k$ dòng cuối, mỗi dòng chứa hai số nguyên $a_i$, $b_i$ mô tả một tuyến giao hàng.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng chi phí nhỏ nhất có thể đạt được.

Ràng buộc

• $2\le n\le 1000$
• $n-1\le m\le min(1000,\frac{n(n-1)}{2})$
• $1\le k\le 1000$
• $1\le x_i,y_i\le n$, $x_i\ne y_i$, $1\le w_i\le 1000$
• $1\le a_i,b_i\le n$
• Đồ thị liên thông và giữa mỗi cặp đỉnh có nhiều nhất một cạnh trực tiếp.

Ví dụ