#include <fstream>
#include <iostream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int inf=30000;
int n,m,i,dim,k;
int heap[50001],poz[50001],dis[50001];
struct vecin{
    int nod,cost;
    vecin *urmator;
} *a[50001];
void adauga(int rad,int num,int c){
    vecin *p;
    p=new vecin;
    p->nod=num;
    p->cost=c;
    p->urmator=a[rad];
    a[rad]=p;
}
int tata(int x){
    return x/2;}
int fiu(int x){
    return x*2;}
void schimba(int x,int y){
    int aux=heap[x];
    heap[x]=heap[y];
    heap[y]=aux;
}
void scufunda(int indice){
    int minim;
    if(fiu(indice)<=dim && dis[heap[fiu(indice)]]<dis[heap[indice]]){
        minim=fiu(indice);}
    else minim=indice;
    if(fiu(indice)<dim && dis[heap[fiu(indice)+1]]<dis[heap[minim]]){
        minim=fiu(indice)+1;}
    if(minim!=indice){
        schimba(indice,minim);
        poz[heap[indice]]=minim;
        poz[heap[minim]]=indice;
        scufunda(minim);
    }
}
void ridica(int indice){
    while(indice>1){
        if(dis[heap[tata(indice)]]>dis[heap[indice]]){
            poz[heap[tata(indice)]]=indice;
            poz[heap[indice]]=tata(indice);
            schimba(indice,tata(indice));
            indice=tata(indice);
        }
        else indice=1;
    }
}
void dijkstra(){
    if(dim==0)return;
    int ind=heap[1];
    schimba(1,dim);
    dim--;
    poz[heap[1]]=1;
    scufunda(1);
    vecin *t;
    t=a[ind];
    while(t){
        if(dis[ind]+t->cost<dis[t->nod]){
            dis[t->nod]=dis[ind]+t->cost;
            if(poz[t->nod]==-1){
                dim++;
                heap[dim]=t->nod;
                poz[t->nod]=dim;
                ridica(dim);
            }
            else ridica(poz[t->nod]);
        }
        t=t->urmator;
    }
    dijkstra();
}
int main(){
    int x,y,z;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>z;
        adauga(x,y,z);
    }
    for(i=2;i<=n;i++){
        dis[i]=inf;
        poz[i]=-1;}
    dis[1]=0;
    heap[++dim]=1;
    dijkstra();
    for(i=2;i<=n;i++){
        if(dis[i]==inf)g<<0<<' ';
        else g<<dis[i]<<' ';}
    g<<'\n';
    return 0;
}