Chính quyền thành phố đã đo đạc khoảng cách ngắn nhất giữa mọi cặp địa điểm trong tổng số \(N\) địa điểm. Do nhu cầu phát triển, thành phố dự định xây thêm lần lượt \(Q\) con đường một chiều mới. Sau mỗi con đường được thêm vào, bạn cần tính tổng khoảng cách ngắn nhất giữa tất cả các cặp địa điểm có thể đi lại được.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 300\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên biểu thị ma trận khoảng cách ngắn nhất ban đầu. Nếu không có đường đi giữa \(i\) và \(j\), khoảng cách được biểu diễn bằng -1. Khoảng cách giữa \(i\) tới chính nó bằng \(0\).
• Dòng tiếp theo chứa số nguyên \(Q\) (\(1 \le Q \le 5\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\), \(W\) (\(1 \le u, v \le N\), \(0 \le W \le 10^5\)), biểu thị một con đường một chiều được xây mới từ \(u\) tới \(v\) với chi phí \(W\).

Định dạng đầu ra

• In ra \(Q\) dòng, mỗi dòng chứa một số nguyên duy nhất là tổng khoảng cách ngắn nhất giữa tất cả các cặp địa điểm liên thông (khoảng cách khác \(-1\)) sau khi thêm con đường tương ứng.

Ràng buộc

• Subtask 1 (40% số điểm): \(N \le 50\), \(Q \le 2\).
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm.