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 đã 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 \neq j \le n} d_{ij}~, trong đó ~d_{ij}~ là đường đi ngắn nhất từ nút ~i~ đến nút ~j~. 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.

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.

Input

• Dòng đầu tiên chứa 3 số nguyên dương ~n, m, k~ (~n \le 400; m \le 10000~);
• Dòng thứ ~s~ (~s = 1, 2, ..., 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, ..., k~) trong ~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, ..., 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. 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.

Output

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

Sample Input 1

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

Sample Output 1

183

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ó ~k \le 400~.