#include <fstream>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int a[1001][1001];
int n,m,d[1001],t[1001],viz[1001];
int inf=1000000000;
void citire(){
    in>>n>>m;
    int x,y,c;
    for(int i=1;i<=m;i++){
        in>>x>>y>>c;
        a[x][y]=c;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j && a[i][j]==0)
                a[i][j]=inf;
}
void dijkstra(){
    for(int j=1;j<=n;j++)
        d[j]=a[1][j];
    viz[1]=1;
    for(int j=2;j<=n;j++)
        if(d[j]<inf)
            t[j]=1;
    for(int k=1;k<=n-1;k++){
        int dmin=inf,poz;
        for(int j=2;j<=n;j++)
            if (!viz[j])
            if(d[j]<dmin){
                dmin=d[j];
                poz=j;
            }
        viz[poz]=1;
        for(int j=2;j<=n;j++){
            if (!viz[j])
            if(d[poz]+a[poz][j]<d[j]){
                d[j]=d[poz]+a[poz][j];
                t[j]=poz;
            }
        }
    }
}
int main()
{
    citire();
    dijkstra();
    for(int i=2;i<=n;i++)
        if(d[i]<inf)
            out<<d[i]<<" ";
        else
            out<<"0 ";
    return 0;
}