#include<bits/stdc++.h>
using namespace std;
int main(){
  int n, m;
  cin >> n >> m;
  int d[n + 7][n + 7];
  for(int i = 1;i <= n;i++){
    for(int j = 1;j <= n;j++){
      d[i][j] = INT_MAX;
      if(i == j)
        d[i][j] = 0;;
    }
  }
  for(int i = 0, a, b, c;i < m;i++){
    cin >> a >> b >> c;
    d[a][b] = c;
  }
  for(int k = 1;k <= n;k++){
    for(int j = 1;j <= n;j++){
      for(int i = 1;i <= n;i++){
        if(d[i][k] < INT_MAX && d[k][j] < INT_MAX)
          d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
  for(int i = 1;i <= n;i++){
    for(int j = 1;j <= n;j++){
      for(int t = 1;t <= n;t++){
        if(d[i][t] < INT_MAX && d[t][t] < 0 && d[t][j] < INT_MAX)
          d[i][j] = INT_MIN;
      }
    }
  }
  for(int i = 1;i <= n;i++){
    for(int j = 1;j <= n;j++){
      if(d[i][j] == INT_MAX) cout << "* ";
      else if(d[i][j] == INT_MIN) cout << "-oo ";
      else if(i == j) cout << min(0, d[i][j]) << ' ';
      else cout << d[i][j] << ' ';
    }
    cout << '\n';
  }
}