ct25c.java

import java.io.*;
import java.util.*;

public class ct25c
{
    private static Reader in;
    private static PrintWriter out;

    public static void main (String [] args) throws IOException {
        in = new Reader ();
        out = new PrintWriter (System.out, true);
        int n = in.nextInt ();
        int [][] grid = new int [n][n];
        int sum = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                grid [i][j] = in.nextInt ();
                if (i > j) sum += grid [i][j];
            }
            
        int k = in.nextInt ();
        while (k-- > 0) {
            int a = in.nextInt () - 1, b = in.nextInt () - 1, c = in.nextInt ();
            if (c > grid [a][b]) {
                out.println (sum);
                continue;
            }
            sum -= grid [a][b] - c;
            grid [a][b] = grid [b][a] = c;
            for (int i = 0; i < n; i++) {
                if (grid [a][b] + grid [b][i] < grid [a][i]) {
                    sum -= grid [a][i] - grid [a][b] - grid [b][i];
                    grid [i][a] = grid [a][i] = grid [a][b] + grid [b][i];
                }
                if (grid [b][a] + grid [a][i] < grid [b][i]) {
                    sum -= grid [b][i] - grid [b][a] - grid [a][i];
                    grid [i][b] = grid [b][i] = grid [b][a] + grid [a][i];
                }
                for (int j = 0; j < n; j++) {
                    if (grid [i][a] + grid [a][b] + grid [b][j] < grid [i][j]) {
                        sum -= grid [i][j] - grid [i][a] - grid [a][b] - grid [b][j];
                        grid [i][j] = grid [j][i] = grid [i][a] + grid [a][b] + grid [b][j];
                    }
                    if (grid [i][b] + grid [b][a] + grid [a][j] < grid [i][j]) {
                        sum -= grid [i][j] - grid [i][b] - grid [b][a] - grid [a][j];
                        grid [i][j] = grid [j][i] = grid [i][b] + grid [a][b] + grid [b][j];
                    }
                }
            }
            out.println (sum);
        }
    }
}

/** Faster input **/
class Reader {
    final private int BUFFER_SIZE = 1 << 16;private DataInputStream din;private byte[] buffer;private int bufferPointer, bytesRead;
    public Reader(){din=new DataInputStream(System.in);buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;}
    public Reader(String file_name)throws IOException{din=new DataInputStream(new FileInputStream(file_name));buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;}
    public String readLine()throws IOException{byte[] buf=new byte[1024];int cnt=0,c;
        while((c=read())!=-1){if(c=='\n')break;buf[cnt++]=(byte)c;}return new String(buf,0,cnt);}
    public int nextInt()throws IOException{int ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');
        if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;} 
    public long nextLong()throws IOException{long ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');
        if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;}
    public double nextDouble()throws IOException{double ret=0,div=1;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c = read();do {ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');
        if(c=='.')while((c=read())>='0'&&c<='9')ret+=(c-'0')/(div*=10);if(neg)return -ret;return ret;}
    private void fillBuffer()throws IOException{bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);if(bytesRead==-1)buffer[0]=-1;}
    private byte read()throws IOException{if(bufferPointer==bytesRead)fillBuffer();return buffer[bufferPointer++];}
    public void close()throws IOException{if(din==null) return;din.close();}
}