Hệ thống mạng truyền thông của một công ty tỉnh Long An bao gồm $n$ máy tính và $m$ kênh nối trực tiếp một chiều giữa hai máy. Các máy tính được đánh số từ $1$ đến $n$, mỗi kênh nối có có dạng $(u, v, t)$ nghĩa là có một kênh nối từ máy $u$ đến máy $v$ với thời gian truyền tin là $t$.

Để đánh giá hiệu suất của hệ thống, công ty đã làm việc dựa trên giá trị $D$. Giá trị $D$ này có thể được tính bằng tổng thời gian truyền tin ít nhất giữa tất cả các cặp máy tính trong hệ thống. Cụ thể, gọi $d(u, v)$ là thời gian truyền tin ít nhất từ máy $u$ đến máy $v$ thì giá trị $D$ được tính theo công thức:

$$D = \sum_{1 \, \leq \, u \, \neq \, v \, \leq \, n} d(u, v)$$

Do bị phàn nàn quá nhiều về chất lượng mạng nên trong thời gian sắp tới, công ty sẽ bổ sung thêm $n'$ máy tính (các máy này dược đánh số từ $n + 1$ đến $n + n'$) và $m'$ kênh nối trực tiếp một chiều liên quan đến những đến những máy này vào hệ thống mạng (tức là ít nhất một trong hai máy tính giữa mỗi kênh nối là máy được bổ sung). Có $q$ giả định bổ sung vào hệ thống mạng như vậy, với mỗi giả định, hãy tính giá trị $D$ trên hệ thống mạng mới.

Lưu ý rằng đây chỉ là giả định. Nghĩa là sau mỗi giả định, hệ thống mạng mới sẽ quay trở về hệ thống mạng ban đầu.

Dữ liệu

• Dòng đầu tiên chứa ba số nguyên $n$, $m$ và $q$ $(2 \leq n \leq 500, 2 \leq m \leq 5000, 0 \leq q \leq 50)$ lần lượt là số máy tính, kênh nối và giả định.
• Trong $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u$, $v$ và $t$ $(1 \leq u \neq v \leq n, 1 \leq t \leq 10^9)$ mô tả một kênh nối.
• Trong $q$ nhóm dòng tiếp theo:
  • Dòng đầu tiên chứa hai số nguyên $n'$ và $m'$ $(1 \leq n' \leq 5, 2 \leq m' \leq 50)$ lần lượt là số máy tính và kênh nối được bổ sung.
  • Trong $m'$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u'$, $v'$ và $t'$ $(1 \leq u' \neq v' \leq n + n', n + 1 \leq \max(u', v') \leq n + n', 1 \leq t' \leq 10^9)$ mô tả một kênh nối được bổ sung.
• Dữ liệu đảm bảo luôn tồn tại đường truyền giữa hai máy bất kỳ.

Kết quả

• Dòng đầu tiên chứa một số nguyên là giá trị $D$ của hệ thống mạng ban đầu.
• Trong $q$ dòng tiếp theo, mỗi dòng chứa một số nguyên là giá trị $D$ của hệ thống mạng mới.

Giới hạn

• Subtask $1$ $(20\%)$: $q = 0$.
• Subtask $2$ $(15\%)$: $q = 1$.
• Subtask $3$ $(15\%)$: $q \leq 5$.
• Subtask $4$ $(25\%)$: Nếu tồn tại kênh nối $(u, v, t)$ thì cũng tồn tại kênh nối $(v, u, t)$ trong cả hệ thống mạng ban đầu lẫn hệ thống mạng mới.
• Subtask $5$ $(25\%)$: Không có ràng buộc gì thêm.

Ví dụ

Dữ liệu

3 3 1
1 2 1
2 3 2
3 1 3
3 5
1 4 1
4 5 2
5 6 3
6 3 4
6 1 5

Kết quả

18
174

Giải thích

Hình minh hoạ ví dụ (đỉnh và cạnh màu xanh đại diện cho máy tính và kênh nối được bổ sung trong giả định):

Trong hệ thống mạng ban đầu, $D = d(1, 2) + d(1, 3) + d(2, 1) + d(2, 3) + d(3, 1) + d(3, 2) = 1 + 3 + 5 + 2 + 3 + 4 = 18$.

Trong hệ thống mạng mới, một số giá trị $d$ là $d(1, 6) = 6$, $d(2, 5) = 8$, $d(6, 1) = 5$, $d(5, 2) = 9$.