#include <bits/stdc++.h>
using namespace std;
long long adj[305][305];
int main() {
  long long n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> adj[i][j];
    }
  }
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (i == j) {
          continue;
        }
        adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
      }
    }
  }
  int k;
  cin >> k;
  for (int i = 0; i < k; i++) {
    long long u, v, w;
    cin >> u >> v >> w;
    if (adj[u][v] > w) {
      adj[u][v] = adj[v][u] = min(adj[u][v], w);
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          if (i == j) {
            continue;
          }
          adj[i][j] = adj[j][i] =
              min(adj[i][u] + adj[u][j], min(adj[i][j], adj[i][v] + adj[v][j]));
        }
      }
    }
    long long t = 0;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        t += adj[i][j];
      }
    }
    cout << t / 2 << " ";
  }
  return 0;
}
