#include<fstream>
#include<vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int vl[50002];
int hp[100002];
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;
        }
        else{
            aux=hp[i];
            hp[i]=hp[i<<1+1];
            hp[i<<1+1]=aux;
        }
    }
    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;
        }
        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];insertheap(g[nod][i].nda);}
    }
    for(i=2;i<=n;i++)
        fout<<vl[i]<<" ";
    fout<<'\n';
    fin.close();
    fout.close();
    return 0;
}