#include <bits/stdc++.h>
using namespace std;
const int MAX = 1010;
int n, m;
int a[MAX][MAX];
int dist[MAX], v[MAX];
void init() {
  int i, j;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      if (i == j)
        a[i][i] = 0;
      else
        a[i][j] = 0x3f3f3f;
    }
  }
}
void floyd(int x, int y) {
  int i, j;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) {
      if (a[i][j] > a[i][x] + a[x][j]) a[i][j] = a[i][x] + a[x][j];
      if (a[i][j] > a[i][y] + a[y][j]) a[i][j] = a[i][y] + a[y][j];
      a[j][i] = a[i][j];
    }
}
int main() {
  int i, j, t;
  while (~scanf("%d", &n)) {
    for (i = 1; i <= n; i++) {
      for (j = 1; j <= n; j++) {
        scanf("%d", &a[i][j]);
      }
    }
    scanf("%d", &m);
    long long sum = 0;
    while (m--) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      if (a[x][y] > z)
        a[x][y] = a[y][x] = z;
      else if (sum != 0) {
        printf("%d ", sum);
        continue;
      }
      floyd(x, y);
      sum = 0;
      for (i = 1; i <= n - 1; i++) {
        for (j = i + 1; j <= n; j++) {
          sum += a[i][j];
        }
      }
      printf("%lld ", sum);
    }
  }
  return 0;
}
