#include <bits/stdc++.h>
using namespace std;
const int maxn = 300 + 66;
const long long mod = 1e9 + 7;
int N, M, Q;
int a[maxn][maxn];
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      scanf("%d", &a[i][j]);
    }
  }
  scanf("%d", &Q);
  int u, v, w;
  while (Q--) {
    scanf("%d %d %d", &u, &v, &w);
    if (a[u][v] > w) {
      a[u][v] = min(w, a[u][v]);
      a[v][u] = min(w, a[u][v]);
      for (int j = 1; j <= N; j++) {
        for (int i = 1; i <= N; i++) {
          a[i][j] = a[j][i] = min(a[j][i], a[j][u] + a[u][i]);
        }
      }
      for (int j = 1; j <= N; j++) {
        for (int i = 1; i <= N; i++) {
          a[i][j] = a[j][i] = min(a[j][i], a[j][v] + a[v][i]);
        }
      }
    }
    long long s = 0;
    for (int i = 1; i <= N; i++) {
      for (int j = i + 1; j <= N; j++) {
        s += a[i][j];
      }
    }
    printf("%lld ", s);
  }
}
