#include <iostream>
#include <fstream>
#define INF 40000
#define NVF 50000
#define NMC 250000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
long long int d[NVF],tata[NVF],n,m,c[10000][10000];
void bellman_Ford(int x)
{
    int ok,i,j,k;
    for(i=1;i<=n;i++)
    {
        tata[i]=0;
        d[i]=INF;
    }
    d[x]=0;
    for(i=1;i<=n;i++)
    {
        ok=0;
        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++)
                if(d[j]!=INF && c[j][k]!=INF)
                    if(d[k]>d[j]+c[j][k])
                    {
                        d[k]=d[j]+c[j][k];
                        tata[k]=j;
                        ok=1;
                    }
    }
}
int main()
{
    int i,x,y,cost,j;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i==j)
                c[i][j]=0;
            else
                c[i][j]=INF;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        c[x][y]=cost;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            cout<<c[i][j]<<" ";
        cout<<endl;
    }
    bellman_Ford(1);
    for(i=2;i<=n;i++)
        fout<<d[i]<<" ";

}