#include <bits/stdc++.h>
using namespace std;
struct FastReader {
  inline int Int() {
    int ch, nag = 0, x = 0;
    while (!isdigit(ch = getchar())) nag = ch == '-';
    x = ch - '0';
    while (isdigit(ch = getchar())) x = x * 10 + ch - '0';
    return nag ? -x : x;
  }
  inline long long Long() {
    long long ch, nag = 0, x = 0;
    while (!isdigit(ch = getchar())) nag = ch == '-';
    x = ch - '0';
    while (isdigit(ch = getchar())) x = x * 10 + ch - '0';
    return nag ? -x : x;
  }
  inline long long Mod(long long P) {
    long long ch, nag = 0, x = 0;
    while (!isdigit(ch = getchar())) nag = ch == '-';
    x = (ch - '0') % P;
    while (isdigit(ch = getchar())) (x = x * 10 + ch - '0') % P;
    return nag ? -x : x;
  }
  inline long double Double() {
    long long a = Int(), b = 0, c = 1, ch;
    while (isdigit(ch = getchar())) b = b * 10 + ch - '0', ch *= 10;
    return a + 1. * b / c;
  }
  inline long long DoubleInt(long long bs = -1) {
    long long a = Int(), b = 0, c = 1, ch;
    while (isdigit(ch = getchar())) b = b * 10 + ch - '0', ch *= 10;
    return bs == -1 ? a * c + b : a * bs + b;
  }
  inline char Alpha() {
    char ch;
    while (!isalpha(ch = getchar()))
      ;
    return ch;
  }
  inline char Char() {
    char ch;
    while (isspace(ch = getchar()))
      ;
    return ch;
  }
  inline char Digit() {
    char ch;
    while (!isdigit(ch = getchar()))
      ;
    return ch;
  }
  inline int CStr(char* c) {
    scanf("%s", c);
    return strlen(c);
  }
  inline int Str(string& s, int len = 3000) {
    char buf[len];
    int l = CStr(buf);
    s = buf;
    return l;
  }
  inline long long operator()() { return Long(); }
} R;
struct FastWriter {
  inline void Int(long long x) {
    if (x < 0) {
      putchar('-');
      return Int(-x);
    }
    if (x / 10) Int(x / 10);
    putchar(x % 10 + '0');
  }
  inline void Char(char x) { putchar(x); }
  inline void Str(const char* x) { printf("%s", x); }
  inline void StrE(const char* x) { puts(x); }
  inline void Eoln() { putchar('\n'); }
  inline void operator()(long long x) { Int(x); }
  inline void operator()(const char* x) { Str(x); }
} W;
long long a[305][305];
int main() {
  int n = R();
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) a[i][j] = R();
  int k = R();
  while (k--) {
    long long x = R(), y = R(), z = R();
    a[x][y] = min(a[x][y], z);
    a[y][x] = min(a[y][x], z);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) {
        a[i][j] = min(a[i][j], a[i][x] + a[x][j]);
        a[j][i] = min(a[j][i], a[j][x] + a[x][i]);
        a[i][j] = min(a[i][j], a[i][y] + a[y][j]);
        a[j][i] = min(a[j][i], a[j][y] + a[y][i]);
      }
    long long sum = 0;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) sum += a[i][j];
    W(sum >> 1);
    W(" ");
  }
  return 0;
}
