#include<fstream>
#include<vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int vl[50002];
int nrnd[50002];
int hp[50002];
int inf=1<<30;
struct ad{
    int nda,val;
};
int lhp=0;
vector<ad>g[50002];
int extract(){
    int ex=hp[1],aux,i=1;
    hp[i]=hp[lhp];
    lhp--;
    while((i<<1<=lhp&&vl[hp[i]]>vl[hp[i<<1]])||((i<<1)+1<=lhp&&vl[hp[i]]>vl[hp[i<<1]])){
        if(vl[hp[i]]>vl[hp[i<<1]]&&(vl[hp[i<<1]]<vl[hp[(i<<1)+1]]||(i<<1)+1>lhp)){
            aux=hp[i];
            hp[i]=hp[i<<1];
            hp[i<<1]=aux;
            nrnd[hp[i]]=i;
            nrnd[hp[i<<1]]=i<<1;
        }
        else{
            aux=hp[i];
            hp[i]=hp[(i<<1)+1];
            hp[(i<<1)+1]=aux;
            nrnd[hp[i]]=i;
            nrnd[hp[(i<<1)+1]]=(i<<1)+1;
        }
    }
    nrnd[ex]=0;
    return ex;
}
void insertheap(int elem){
    ++lhp;
    hp[lhp]=elem;
    int n=lhp,aux;
    while(n>1){
        if(vl[hp[n]]<vl[hp[n>>1]]){
            aux=hp[n];
            hp[n]=hp[n>>1];
            hp[n>>1]=aux;
            nrnd[hp[n]]=n;
            nrnd[hp[n>>1]]=n>>1;
        }
        n>>=1;
    }
}
void updateheap(int n){
    int aux;
    while(n>1){
        if(vl[hp[n]]<vl[hp[n>>1]]){
            aux=hp[n];
            hp[n]=hp[n>>1];
            hp[n>>1]=aux;
            nrnd[hp[n]]=n;
            nrnd[hp[n>>1]]=n>>1;
        }
        n>>=1;
    }
}
int main(){
    int n,m,i,a,b,c,cn;
    ad aux;
    int nod;
    fin>>n>>m;
    vl[1]=0;
    for(i=2;i<=n;i++)
        vl[i]=inf;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        aux.nda=b;
        aux.val=c;
        g[a].push_back(aux);
    }
    insertheap(1);
    cn=n;
    while(cn){
        cn--;
        nod=extract();
        i=0;
        for(i=0;i<g[nod].size();i++)
            if(g[nod][i].val+vl[nod]<vl[g[nod][i].nda]){
                    vl[g[nod][i].nda]=g[nod][i].val+vl[nod];
                    if(nrnd[g[nod][i].nda])updateheap(nrnd[g[nod][i].nda]);
                    else insertheap(g[nod][i].nda);
            }
    }
    for(i=2;i<=n;i++)
        fout<<vl[i]<<" ";
    fout<<'\n';
    fin.close();
    fout.close();
    return 0;
}