#include <bits/stdc++.h>
using namespace std;
long long d[305][305];
long long n;
void compute(long long u) {
  for (long long i = 1; i <= n; i++) {
    for (long long j = 1; j <= n; j++) {
      d[i][j] = min(d[i][j], d[i][u] + d[u][j]);
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (long long i = 1; i <= n; i++)
    for (long long j = 1; j <= n; j++) cin >> d[i][j];
  long long k;
  cin >> k;
  while (k--) {
    long long u, v, c;
    cin >> u >> v >> c;
    d[u][v] = min(d[u][v], c);
    d[v][u] = min(d[v][u], c);
    long long sum = 0;
    for (long long i = 1; i <= n; i++) {
      d[u][i] = min(d[u][i], d[u][v] + d[v][i]);
      d[i][u] = d[u][i];
    }
    for (long long i = 1; i <= n; i++) {
      d[v][i] = min(d[v][i], d[v][u] + d[u][i]);
      d[i][v] = d[v][i];
    }
    compute(u);
    compute(v);
    for (long long i = 1; i <= n; i++)
      for (long long j = i + 1; j <= n; j++) sum += d[i][j];
    cout << sum << " ";
  }
}
