题目描述

现有一张 $n$ 个点的无向图 G，给出其两两的最短路长度。

有 $k$ 次操作，每次会给该图加一条无向边 $(a_i,b_i)$，边权为 $c_i$，求每次加边后两两最短路的长度之和，一对点只计算一次。

输入格式

第一行一个整数 $n$，$2\le n\le 300$。

接下来 $n$ 行，每行 $n$ 个整数 $d_{i,j}$，表示顶点 $i,j$ 之间的最短路长度。

接下来一个整数 $k$，$1\le k\le 300$。

接下来 $k$ 行，每行三个整数 $a_i,b_i,c_i$。边权和给出的最短路长度为不超过 $1000$ 的正整数。

输出格式

输出 $k$ 个整数，为每次操作后的答案，用空格分隔。

2
0 5
5 0
1
1 2 3

3

3
0 4 5
4 0 9
5 9 0
2
2 3 8
1 2 1

17 12