#include <bits/stdc++.h>
using namespace std;
const int maxn = 300 + 10;
long long a[maxn][maxn];
long long c[maxn][maxn];
long long b[maxn][4];
int main() {
  long long n;
  cin >> n;
  for (long long i = 1; i <= n; i++)
    for (long long j = 1; j <= n; j++) cin >> a[i][j];
  long long m;
  cin >> m;
  for (long long i = 1; i <= m; i++) cin >> b[i][1] >> b[i][2] >> b[i][3];
  long long ans = 0;
  for (long long i = 1; i <= n; i++)
    for (long long j = 1; j <= n; j++) ans += a[i][j];
  for (long long k = 1; k <= m; k++) {
    long long x = b[k][1];
    long long y = b[k][2];
    long long z = b[k][3];
    c[x][y] = min(z, a[x][y]);
    c[y][x] = c[x][y];
    for (long long i = 1; i <= n; i++)
      for (long long j = 1; j <= n; j++) {
        c[i][j] =
            min(min(a[i][x] + c[x][y] + a[j][y], a[i][y] + c[x][y] + a[x][j]),
                a[i][j]);
        c[j][i] = c[i][j];
      }
    long long res = 0;
    for (long long i = 1; i <= n; i++)
      for (long long j = 1; j <= n; j++) res += c[i][j];
    ans = min(ans, res);
    cout << ans / 2 << ' ';
    for (long long i = 1; i <= n; i++)
      for (long long j = 1; j <= n; j++) a[i][j] = c[i][j];
    for (long long i = 1; i <= n; i++)
      for (long long j = 1; j <= n; j++) c[i][j] = 0;
  }
  cout << endl;
  return 0;
}
