#include <bits/stdc++.h>
using namespace std;
int n, k, a, b;
long long d[301][301], sum, tmp, c;
int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      cin >> d[i][j];
      d[j][i] = d[i][j];
      sum += d[i][j];
    }
  sum /= 2;
  cin >> k;
  for (int i = 0; i < k; ++i) {
    cin >> a >> b >> c;
    if (d[a][b] > c) {
      sum = sum - d[a][b] + c;
      d[a][b] = d[b][a] = c;
      for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
          if (d[i][j] >= (tmp = d[i][a] + d[a][b] + d[b][j])) {
            sum = sum - d[i][j] + tmp;
            d[i][j] = d[j][i] = tmp;
          }
    }
    cout << sum << " ";
  }
  return 0;
}
