#include <iostream>
#include <fstream>

#define oo 0x3f3f3f

using namespace std;
int n,m,a[100][100];
void init()
{
    ifstream f("test.in");

    f>>n;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)
                a[i][j]=a[j][i]=oo;

    f>>m;
    int x,y; double cs;

    for(int i=1;i<=m;i++)
        {
            f>>x>>y>>cs;
            a[x][y]=cs;
        }
}

void royfloyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
           if(i!=k)
               for(int j=1;j<=n;j++)
                  if(a[i][j]>a[i][k]+a[k][j])
                      a[i][j]=a[i][k]+a[k][j];
}

int main()
{
    ofstream g("test.out");
    init();
    royfloyd();

    for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)

                    g<<a[i][j]<<" ";
            g<<"\n";
        }



    return 0;
}