#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <fstream>

using namespace std;

ifstream f ("royfloyd.in");
ofstream g ("royfloyd.out");
int NRMAX = 1000000;

int main()
{
    int n, m;
    f >> n >> m;

    int dist[n+1][n+1];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j<=n;j++)
            if(i!=j)
                dist[i][j] = NRMAX;
            else
                dist[i][j]=0;

    for(int i = 1; i<=m;i++)
    {
        int u, v, w;
        f >> u >> v >> w;
        dist[u][v] = w;
    }

    for(int k = 1;k<=n;k++)
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=n;j++)
                if(dist[i][k]+dist[k][j]<dist[i][j])
                    dist[i][j]=dist[i][k]+dist[k][j];

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1;j<=n;j++)
            if(dist[i][j] == NRMAX)
                g << 0 << " ";
            else
                g << dist[i][j] << " ";
        g << endl;
    }

    f.close();
    g.close();
    return 0;
}