#include <fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define inf (1<<15)
int n,c[20000][20000],d[50001],t[50001],s[50001],xp=1,m;
void cit(){
    int i,j,x,y,z;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            c[i][j]=inf;
    while(fin){
        fin>>x>>y>>z;
        c[x][y]=z;}
}
int min(int &q){
    int i,m=2*inf;
    for(i=1;i<=n;i++)
        if(!s[i] && d[i]<m){
            m=d[i];
            q=i;}
}
void det_drumuri(){
    int i,x,j,k,ok;
    for(i=1;i<=n;i++){
        d[i]=c[xp][i];
        s[i]=0;
        if(c[xp][i]<inf)
            t[i]=xp;
        else
            t[i]=0;}
    s[xp]=1;
    t[xp]=0;
    ok=1;
    x=0;
    do{ min(k);
        x++;
        if(d[k]==inf || x==n)
            ok=0;
        else{
            s[k]=1;
            for(j=1;j<=n;j++)
                if(!s[j] && d[j]>d[k]+c[k][j]){
                    d[j]=d[k]+c[k][j];
                    t[j]=k;}
}
    }while(ok);
}
void drum(int i){
    if(i){
        drum(t[i]);
        fout<<i<<" ";}
}
/*void afis_drumuri(){
    int i;
    for(i=1;i<=n;i++)
        if(i!=xp)
            if(d[i]==inf)
                fout<<"nu exista drum de la "<<xp<<" la "<<i<<'\n';
            else{
                fout<<"drumul minim de la "<<xp<<" la "<<i<<" este\n";
                drum(i);fout<<'\n';
                fout<<"lungimea drumului este "<<d[i]<<'\n';
            }
    }*/
int main()
{
    cit();
    det_drumuri();
    for(int i=2;i<=n;i++)
        fout<<d[i]<<" ";
    return 0;
}