#include <bits/stdc++.h>
using namespace std;
void vec(vector<int> &v) {
  for (int i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
  cout << endl;
}
void vec_ll(vector<long long int> &v) {
  for (int i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
  cout << endl;
}
struct cmp {
  bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
    int lena = a.second - a.first + 1;
    int lenb = b.second - b.first + 1;
    if (lena == lenb) {
      return a.first < b.first;
    }
    return lena > lenb;
  }
};
bool sortinrev(const pair<int, int> &a, const pair<int, int> &b) {
  return (a.first > b.first);
}
int maxin(vector<int> &v, int a, int b) {
  int maxi = INT_MIN;
  int ind = -1;
  for (int i = a; i <= b; i++) {
    if (maxi < v[i]) {
      maxi = v[i];
      ind = i;
    }
  }
  return ind;
}
long long power(int base, int exp) {
  long long a = 1;
  for (int i = 1; i <= exp; i++) {
    a *= base;
  }
  return a;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n;
  cin >> n;
  vector<vector<long long int>> adj(n, vector<long long int>(n, 1e9));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> adj[i][j];
    }
  }
  vector<vector<long long int>> v = adj;
  int k;
  cin >> k;
  long long int prev = -1;
  for (int q = 0; q < k; q++) {
    int a, b, c;
    cin >> a >> b >> c;
    if (v[a - 1][b - 1] > c) {
      v[a - 1][b - 1] = c;
      v[b - 1][a - 1] = c;
      long long int sum = 0;
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          v[i][j] = min(v[i][j], v[i][a - 1] + c + v[b - 1][j]);
          v[i][j] = min(v[i][j], v[i][b - 1] + c + v[a - 1][j]);
          sum += v[i][j];
        }
      }
      prev = sum / 2;
      cout << sum / 2 << endl;
    } else {
      if (prev != -1) {
        cout << prev << endl;
      } else {
        long long int sum = 0;
        for (int i = 0; i < n; i++) {
          for (int j = 0; j < n; j++) {
            sum += v[i][j];
          }
        }
        prev = sum / 2;
        cout << prev << endl;
      }
    }
  }
}
