#include <bits/stdc++.h>
#define Nmax 1505
using namespace std;
ifstream fin ("graph.in");
ofstream fout ("graph.out");
struct muchie
{
    int x, c;
};
vector <muchie> v[Nmax];
vector <int> d[Nmax];
int a[Nmax][Nmax], u[Nmax][Nmax], viz[Nmax], n, m, x, y, c;
void dfs(int x)
{
    d[x].push_back(x);
    a[x][x]=1;
    viz[x]=1;
    for(int i=0;i<v[x].size();i++)
        {
            int f = v[x][i].x;
            if(!viz[f])
                dfs(f);
            for(int j=0;j<d[f].size();j++)
            {
                int n=d[f][j];
                if(a[x][n]==0)
                {
                    a[x][n]=1;
                    d[x].push_back(n);
                    u[x][n]=u[f][n]+v[x][i].c;
                }
                else u[x][n]=min(u[x][n], u[f][n]+v[x][i].c);
            }
        }
}

int main()
{
    fin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        fin >> x >> y >> c;
        v[x].push_back({y, c});
    }
    for(int i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            {
                if(a[i][j])
                    fout << u[i][j] << ' ';
                else fout << "x ";
            }
        fout << '\n';
    }
    return 0;
}