#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  ll N;
  cin >> N;
  ll arr[N][N];
  for (ll i = 0; i < N; i++) {
    for (ll j = 0; j < N; j++) {
      cin >> arr[i][j];
    }
  }
  for (ll k = 0; k < N; k++) {
    for (ll i = 0; i < N; i++) {
      for (ll j = 0; j < N; j++) {
        arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
      }
    }
  }
  ll K;
  cin >> K;
  for (ll i = 0; i < K; i++) {
    ll a, b, l;
    cin >> a >> b >> l;
    a--;
    b--;
    arr[a][b] = min(arr[a][b], l);
    arr[b][a] = min(arr[b][a], l);
    for (ll i = 0; i < N; i++) {
      for (ll j = 0; j < N; j++) {
        arr[i][j] = min(arr[i][j], arr[i][a] + arr[a][b] + arr[b][j]);
        arr[i][j] = min(arr[i][j], arr[i][b] + arr[b][a] + arr[a][j]);
      }
    }
    ll sum = 0;
    for (ll i = 0; i < N; i++) {
      for (ll j = 0; j < N; j++) {
        sum += arr[i][j];
      }
    }
    cout << sum / 2 << '\n';
  }
}
