#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[50000],poz[50000],dis[50000];
bool viz[50000];
struct vecin{
    int nod,cost;
    vecin *urmator;
} *a[50000];
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(int i){
    k++;
    if(k==n)return;
    viz[i]=true;
    vecin *t;
    t=a[i];
    while(t){
        if(dis[i]+t->cost<dis[t->nod]&&!viz[t->nod])
            dis[t->nod]=dis[i]+t->cost;
            if(poz[t->nod]==-1){
                dim++;
                heap[dim]=t->nod;
                ridica(dim);
            }
            else ridica(poz[t->nod]);
        t=t->urmator;
    }
    int aux=heap[1];
    schimba(1,dim);
    dim--;
    poz[heap[1]]=1;
    scufunda(1);
    dijkstra(aux);
}
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;
        viz[i]=false;
        poz[i]=-1;}
    dis[1]=0;
    dijkstra(1);
    for(i=2;i<=n;i++)g<<dis[i]<<' ';
    return 0;
}