Dịch vụ mạng

Hệ thống mạng truyền thông của công ty HP bao gồm $n$ nút và $m$ kênh nối trực tiếp một chiều giữa hai nút. Các nút được đánh số từ $1$ đến $n$. Các kênh nối được đánh số từ $1$ đến $m$. Kênh nối từ nút $i$ tới nút $j$ mất $t_{ij}$ đơn vị thời gian để truyền tin. Có thể có nhiều kênh truyền tin từ một nút đến một nút khác. Để đánh giá hiệu suất hệ thống mạng, công ty đã đánh giá dựa trên giá trị $DIJ$, giá trị $DIJ$ được tính bằng tổng độ dài đường đi ngắn nhất giữa tất cả các cặp nút trong hệ thống mạng, cụ thể $DIJ={\sum }_{1\le i\ne j\le n}{d}_{ij}$, trong đó $d_{ij}$ là độ dài đường đi ngắn nhất từ nút $i$ đến nút $j$ (tổng thời gian truyền tin của các kênh trên đường đi).

Trong thời gian tới, công ty sẽ bổ sung thêm ba nút (ba nút này được đánh số tương ứng là $n+1,n+2,n+3$) và một số kênh nối liên quan đến ba nút này vào hệ thống mạng. Công ty cần tính giá trị $DIJ$ trên hệ thống mạng mới (tổng $d_{ij}$ trên mọi cặp có thứ tự gồm hai nút khác nhau trong số $n+3$ nút).

Yêu cầu: Cho biết hệ thống mạng truyền thông ban đầu của công ty HP và $k$ giả định bổ sung vào hệ thống mạng. Với mỗi giả định, hãy tính giá trị $DIJ$ trên hệ thống mạng mới. Các giả định độc lập với nhau: mỗi giả định chỉ gồm hệ thống mạng ban đầu cùng các kênh của riêng giả định đó.

Dữ liệu vào

• Dòng đầu tiên chứa $3$ số nguyên dương $n,m,k$.
• Dòng thứ $s$ ($s=1,2,\dots ,m$) trong số $m$ dòng tiếp theo ghi ba số nguyên dương $i_s,j_s,t_{i_s{j}_s}$ lần lượt là chỉ số đầu, chỉ số cuối và thời gian truyền tin của kênh thứ $s$.
• Dòng thứ $p$ ($p=1,2,\dots ,k$) trong số $k$ dòng tiếp theo mô tả giả định thứ $p$ có dạng: số đầu tiên là số $e_p$ là số lượng kênh nối liên quan đến ba nút mới thêm vào hệ thống. Tiếp theo là $e_p$ bộ ba số $u_h,v_h,t_{u_h{v}_h}$ ($h=1,2,\dots ,e_p$) lần lượt là chỉ số đầu, chỉ số cuối và thời gian truyền tin của $e_p$ kênh nối bổ sung. Mỗi kênh bổ sung có ít nhất một đầu là một trong ba nút mới.

Dữ liệu đảm bảo có đường truyền tin từ một nút đến một nút bất kì khác, cả trong hệ thống mạng ban đầu và trong hệ thống mạng mới của mọi giả định.

Dữ liệu ra

Gồm $k$ dòng, mỗi dòng chứa một số là giá trị $DIJ$ tương ứng với từng giả định.

Ràng buộc

• $2\le n\le 400$; $n\le m\le {10}^4$; $1\le k\le 400$.
• $1\le i_s,j_s\le n$, $i_s\ne j_s$.
• $1\le e_p\le 100$; $1\le u_h,v_h\le n+3$, $u_h\ne v_h$, $max(u_h,v_h)>n$.
• Mọi thời gian truyền tin là số nguyên trong đoạn $[1,{10}^6]$.

Subtasks

• Có $40\%$ số test ứng với $40\%$ số điểm của bài có $k=1$;
• Có $20\%$ số test khác ứng với $20\%$ số điểm của bài có $k\le 3$;
• Có $40\%$ số test còn lại ứng với $40\%$ số điểm của bài có $k\le 400$.

Ví dụ