#include <bits/stdc++.h>
using namespace std;
int dp[400][400];
int V, K;
int main() {
  scanf("%d", &V);
  long long sum = 0;
  for (int i = 0; i < V; i++)
    for (int j = 0; j < V; j++)
      scanf("%d", &dp[i][j]), sum += (long long)dp[i][j];
  scanf("%d", &K);
  sum /= (long long)2;
  for (int q = 0; q < K; q++) {
    int f, t, c;
    scanf("%d%d%d", &f, &t, &c);
    --f, --t;
    if (dp[f][t] <= c) {
      printf("%I64d\n", sum);
      continue;
    }
    dp[f][t] = dp[t][f] = c;
    sum = 0;
    for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
        dp[i][j] = min(dp[i][j], dp[i][f] + dp[f][t] + dp[t][j]);
        dp[i][j] = min(dp[i][j], dp[i][t] + dp[f][t] + dp[f][j]);
        sum += (long long)dp[i][j];
      }
    }
    sum /= (long long)2;
    printf("%I64d\n", sum);
  }
  return 0;
}
