#include <iostream>
#include<fstream>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int a[100][100],m,n,i,j,dist[100],sursa,selectat[100],nodmin,cmin,x,y,c;

int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            fin>>x>>y>>c;
            a[x][y]=c;
        }
    sursa=1;
    for(i=1;i<=n;i++)
        a[i][i]=0;//0 pe diag principala
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(a[i][j]==0&&i!=j)//daca nu avem drum de la i la j
            a[i][j]=1e9;//este infinit in matricea de adiacenta
    for(i=1;i<=n;i++)
        dist[i]=a[1][i];//consideram drumurile ca au toate drum de la 1
    for(i=1;i<=n;i++){
        cmin=1e9;
        nodmin=-1;
        for(j=1;j<=n;j++)
        if(selectat[j]==0&&dist[j]<cmin){
                cmin=dist[j];
                nodmin=j;
        }
    selectat[nodmin]=1;
    for(j=1;j<=n;j++)
        if(a[nodmin][j]!=0&&dist[j]>a[nodmin][j]+dist[nodmin])
        dist[j]=a[nodmin][j]+dist[nodmin];
    }
    for(i=2;i<=n;i++)
        fout<<dist<<" ";
    return 0;
}