#include <bits/stdc++.h>
using namespace std;
const int MAXN(100010);
const int MAXE(100010);
template <typename T>
bool checkmin(T &a, const T &b) {
  return b < a ? (a = b, true) : false;
}
template <typename T>
bool checkmax(T &a, const T &b) {
  return b > a ? (a = b, true) : false;
}
inline int lowb(int i) { return i & -i; }
int gcd(int a, int b) {
  while (b) {
    int t = a % b;
    a = b;
    b = t;
  }
  return a;
}
long long dis[301][301];
int main() {
  int n, K;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) scanf("%I64d", dis[i] + j);
  scanf("%d", &K);
  for (int i = 0; i < K; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    --u, --v;
    if (w < dis[u][v]) {
      dis[u][v] = dis[v][u] = w;
      for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
          long long t =
              min(dis[i][u] + w + dis[v][j], dis[i][v] + w + dis[u][j]);
          checkmin(dis[i][j], t);
        }
    }
    long long ans = 0;
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j) ans += dis[i][j];
    printf("%I64d\n", ans);
  }
  return 0;
}
