#include <bits/stdc++.h>
long long int tab[305][305];
int n, k;
long long int sum;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) scanf("%lld", &tab[i][j]), sum += tab[i][j];
  scanf("%d", &k);
  while (k--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (tab[a][b] > c) {
      sum -= 2 * tab[a][b];
      tab[b][a] = tab[a][b] = c;
      sum += 2 * c;
      for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
          sum -= 2 * tab[i][j];
          if (tab[i][j] > tab[i][a] + c + tab[b][j])
            tab[i][j] = tab[i][a] + c + tab[b][j];
          if (tab[i][j] > tab[i][b] + c + tab[a][j])
            tab[i][j] = tab[i][b] + c + tab[a][j];
          tab[j][i] = tab[i][j];
          sum += 2 * tab[i][j];
        }
    }
    printf("%lld ", sum / 2);
  }
  printf("\n");
  return 0;
}
