#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;
    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){
    if(indice!=1){
        if(dis[heap[tata(indice)]]>dis[heap[indice]]){
            schimba(tata(indice),indice);
            poz[heap[tata(indice)]]=indice;
            poz[heap[indice]]=tata(indice);
            ridica(tata(indice));
        }
    }
}
void dijkstra(){
    while(dim>0){
        int ind=heap[1];
        schimba(1,dim);
        poz[heap[1]]=1;
        dim--;
        scufunda(1);
        vecin *t;
        t=a[ind];
        while(t){
            if(dis[t->nod]>dis[ind]+t->cost){
                dis[t->nod]=dis[ind]+t->cost;
                if(poz[t->nod]!=-1)
                    ridica(poz[t->nod]);
                else{
                    heap[++dim]=t->nod;
                    poz[t->nod]=dim;
                    ridica(dim);
                }
            }
            t=t->urmator;
        }
    }
}
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;
    poz[1]=1;
    heap[++dim]=1;
    dijkstra();
    for(i=2;i<=n;i++){
        if(dis[i]==inf)g<<0<<' ';
        else g<<dis[i]<<' ';}
    return 0;
}