#include <bits/stdc++.h>
static const int INF = 1 << 25;
static const double EPS = 1e-5;
using namespace std;
typedef pair<int, pair<int, int> > pipii;
void solve() {
  int n, k;
  cin >> n;
  vector<vector<int> > g(n, vector<int>(n));
  for (int i = (int)(0); i < (int)(n); ++i)
    for (int j = (int)(0); j < (int)(n); ++j) cin >> g[i][j];
  cin >> k;
  for (int i = (int)(0); i < (int)(k); ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    --a;
    --b;
    for (int i = (int)(0); i < (int)(n); ++i)
      g[i][a] = g[a][i] = min(g[i][a], g[i][b] + c);
    for (int i = (int)(0); i < (int)(n); ++i)
      g[i][b] = g[b][i] = min(g[i][b], g[i][a] + c);
    for (int i = (int)(0); i < (int)(n); ++i)
      for (int j = (int)(0); j < (int)(n); ++j) {
        g[i][j] = min(g[i][j], g[i][a] + g[b][j] + c);
        g[i][j] = min(g[i][j], g[i][b] + g[a][j] + c);
      }
    long long res = 0;
    for (int i = (int)(0); i < (int)(n); ++i)
      for (int j = (int)(0); j < (int)(i); ++j) res += g[i][j];
    cout << res << endl;
  }
}
int main() {
  solve();
  return 0;
}
