#include <bits/stdc++.h>
using namespace std;
int n, m;
int side[100][100];
int main() {
  memset(side, 63, sizeof(side));
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    side[u][v] = w;
  }
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        side[i][j] = min(side[i][j], side[i][k] + side[k][j]);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cout << side[i][j] << " ";
    }
    cout << endl;
  }
  return 0;
}
