#include <bits/stdc++.h>
using namespace std;
const long long INF = 9999999999;
long long _mat[1000][1000] = {0};
long long cnt;
long long a, b;
long long dj() {
  long long use[1000] = {0};
  long long dis[1000] = {0};
  for (long long i = 1; i <= cnt; i++)
    if (_mat[1][i] != INF)
      dis[i] = 1;
    else
      dis[i] = INF;
  use[1] = 1;
  dis[1] = 0;
  for (long long i = 1; i < cnt; i++) {
    long long min_index;
    long long min_value = INF;
    for (long long j = 2; j <= cnt; j++) {
      if (dis[j] < min_value && use[j] == 0) {
        min_index = j;
        min_value = dis[j];
      }
    }
    if (min_value == INF) break;
    use[min_index] = 1;
    for (long long j = 1; j <= cnt; j++)
      if (_mat[min_index][j] < INF) {
        if (dis[j] > dis[min_index] + _mat[min_index][j])
          dis[j] = dis[min_index] + _mat[min_index][j];
      }
  }
  return dis[cnt];
}
int main() {
  ios::sync_with_stdio(false);
  cin >> cnt;
  for (long long i = 1; i <= cnt; i++)
    for (long long j = 1; j <= cnt; j++) cin >> _mat[i][j];
  for (long long k = 1; k <= cnt; k++)
    for (long long i = 1; i <= cnt; i++)
      for (long long j = 1; j <= cnt; j++)
        if (_mat[i][j] > _mat[i][k] + _mat[k][j])
          _mat[i][j] = _mat[i][k] + _mat[k][j];
  long long case_cnt;
  long long dis;
  cin >> case_cnt;
  for (long long i1 = 0; i1 < case_cnt; i1++) {
    cin >> a >> b >> dis;
    if (dis < _mat[a][b])
      _mat[a][b] = _mat[b][a] = dis;
    else
      dis = _mat[a][b];
    for (long long i = 1; i <= cnt; i++)
      for (long long j = 1; j <= cnt; j++) {
        if (_mat[i][j] > _mat[i][a] + _mat[b][j] + dis)
          _mat[i][j] = _mat[i][a] + _mat[b][j] + dis;
        if (_mat[i][j] > _mat[j][a] + _mat[b][i] + dis)
          _mat[i][j] = _mat[j][a] + _mat[b][i] + dis;
      }
    long long sum = 0;
    for (long long i = 1; i <= cnt; i++)
      for (long long j = 1; j <= i; j++) sum += _mat[i][j];
    cout << sum << ' ';
  }
  cout << endl;
  return 0;
}
