#include <fstream>
#define inf 9999999
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int c[1201][1201],n,m,t[1201],s[1201],r,d[1201],x,y;
void cit(){
    int i,j,h,w;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
                c[i][j]=inf;
    for(h=1;h<=m;h++){
        fin>>i>>j>>w;
        c[i][j]=w;
    }
    fin.close();
}
void dijkstra(int r){
    int i,j,k,Min;
    for(j=1;j<=n;j++)
        d[j]=c[r][j];
    for(i=1;i<=n;i++)
        t[i]=r,s[i]=0;
    t[r]=0;s[r]=1;
    for(k=1;k<n;k++){
        Min=inf;
        for(j=1;j<=n;j++)
            if(s[j]==0&&d[j]<Min){
                i=j;
                Min=d[j];
            }
        s[i]=1;
        for(j=1;j<=n;j++)
            if(d[j]>d[i]+c[i][j]){
                d[j]=d[i]+c[i][j];
                t[j]=i;
            }
    }
}
/*void afis(int i){
    if(i>0){
        afis(t[i]);
        fout<<i<<" ";
    }
}*/
int main(){
    cit();
    dijkstra(1);
    for(int i=1;i<=n;i++)
        if(i!=1){
            fout<<d[i]<<" ";
        }
    return 0;
}