Hay n ciudades numeradas del ~1~ al ~N~ en Berland. Algunos de ellos están conectados por carreteras de doble sentido. Cada camino tiene su propia longitud, un número entero del ~1~ al ~1000~. Se sabe que desde cada ciudad es posible llegar a cualquier otra ciudad por los caminos existentes. También para cada par de ciudades se conoce la distancia más corta entre ellas. El gobierno de Berland planea construir ~K~ nuevas carreteras. Para cada una de las carreteras planificadas se conoce su longitud y las ciudades que conectará. Para controlar la corrección de la construcción de nuevas carreteras, después de la apertura de otra carretera, el gobierno de Berland quiere verificar la suma de las distancias más cortas entre todos los pares de ciudades. Para una matriz dada de distancias más cortas en las carreteras antiguas y los planos de todas las carreteras nuevas, averigüe cómo cambia la suma de las distancias más cortas entre todos los pares de ciudades después de la construcción de cada carretera.

Entrada

La primera línea contiene el número entero ~N (2 \le N \le 300)~ -la cantidad de ciudades en Berland. Luego siguen ~N~ líneas con ~N~ números enteros cada una: la matriz de distancias más cortas. El j-ésimo entero en la i-ésima fila indica la distancia más corta entre las ciudades ~i~ y ~j~. Se garantiza las distancias son longitudes entras de 1 a 1000 y es posible llegar a cualquier otra ciudad utilizando estas carreteras.

La siguiente línea contiene el entero ~K (1 \le K \le 300)~ - cantidad de nuevas carreteras planificadas. Las siguientes ~K~ líneas contienen la descripción de las carreteras planificadas. Cada carretera se describe mediante tres números enteros separados por espacios ~ai~, ~bi~, ~ci~ \((1 \le ai, bi \le n, ai ≠ bi, 1 \le ci \le 1000)\) - ~ai~ y ~bi~ - par de ciudades, que conecta la carretera, ~ci~ - la longitud del camino. Pueden ser varias carreteras entre un par de ciudades, pero ninguna carretera conecta la ciudad consigo misma.

Salida

Salida ~K~ enteros separados por espacios ~qi (1 \le i \le K)~. ~qi~ debe ser igual a la suma de las distancias más cortas entre todos los pares de ciudades después de la construcción de carreteras con índices de ~1~ a ~i~. Las carreteras se numeran desde ~1~ en el orden de entrada. Cada par de ciudades debe tenerse en cuenta en la suma exactamente una vez, solo contamos pares desordenados.

Entrada de ejemplo 1:

2
0 5
5 0
1
1 2 3

Salida de ejemplo 1:

3

Entrada de ejemplo 2:

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

Salida de ejemplo 2:

17 12