#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
const int N = 310;
long long n, k, m, x, y, w;
long long d[N][N];
long long min(long long x, long long y) { return x < y ? x : y; }
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) cin >> d[i][j];
  cin >> k;
  for (int z = 1; z <= k; z++) {
    cin >> x >> y >> w;
    d[x][y] = min(d[x][y], w);
    d[y][x] = min(d[y][x], w);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) {
        d[i][j] = min(d[i][j], d[i][x] + w + d[y][j]);
        d[i][j] = min(d[i][j], d[i][y] + w + d[x][j]);
      }
    long long sum = 0;
    for (int i = 1; i <= n; i++)
      for (int j = i + 1; j <= n; j++) sum += d[i][j];
    cout << sum << " ";
  }
  return 0;
}
