#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;
int n, m, i, j, k, c, a[105][105];
int main()
{
    ifstream f("royfloyd.in");
    ofstream g("royfloyd.out");
    f >> n >> m;
    for(i = 1; i <= n; i ++)
    {
        for(j = 1; j <= n; j ++)
          a[i][j] = INF;
        a[i][i] = 0;
    }
    while(m)
    {
        f >> i >> j >> c;
        a[i][j] = c;
        m --;
    }
    for(k = 1; k <= n; k ++)
      for(i = 1; i <= n; i ++)
        for(j = 1; j <= n; j ++)
          if(a[i][j] > a[i][k] + a[k][j])
            a[i][j] = a[i][k] + a[k][j];
    for(i = 1; i <= n; i ++)
    {
        for(j = 1; j <= n; j ++)
          if(a[i][j] == INF) g << -1 << " ";
                 else g << a[i][j] << " ";
        g << "\n";
    }
    return 0;
}