#include <iostream>
#include <fstream>
#define inf 1<<28
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct Muchie{
    int b,c;
    Muchie * urmatoarea;
};
Muchie* V[50001];
int H[50001],poz[50001],D[50001],g1,n,m,k;
void add(int a,int b1,int c1){
    Muchie * p;
    p=new Muchie;
    p->b=b1;
    p->c=c1;
    p->urmatoarea=V[a];
    V[a]=p;
}
void read(){
    f>>n>>m;
    for(int i=0,a,b,c;i<m;i++){
        f>>a>>b>>c;
        add(a,b,c);

    }
}
void swapheap(int a,int b){
    swap(H[a],H[b]);
    poz[H[a]]=b;
    poz[H[b]]=a;
}
void upheap(int w){
    int tata=w>>1;
    while(tata){
        if(D[tata]>D[w]){
            swapheap(tata,w);
            w=tata;
            tata=w>>1;
        }else{
            tata=0;
        }
    }
}
void downheap(int w){
    int f=w<<1;
    while(f<=k){
        if(D[f]>D[f+1]){
            f++;
        }
        if(D[f]<D[w]){
            swap(f,w);
            w=f;
            f=w<<1;
        }else{
            f=k+1;
        }
    }
}
void dijkstra(int nod){
    for(int i=2;i<=n;i++){
        D[i]=inf;poz[i]=-1;
    }
    H[++k]=nod;
    poz[H[k]]=k;
    while(k){
        int min=H[1];
        swapheap(1,k);
        poz[H[1]]=1;
        k--;
        downheap(1);
        Muchie * a=V[min];
        while(a){
            if(D[a->b]>D[min]+a->c){
                D[a->b]=D[min]+a->c;
                if(poz[a->b]!=-1){
                    upheap(poz[a->b]);
                }else{
                    H[++k]=a->b;
                    poz[H[k]]=k;
                    upheap(k);
                }
            }
            a=a->urmatoarea;
        }
    }

}
int main()
{
    read();
    dijkstra(1);
    for(int i=2;i<=n;i++){
        g<<D[i]<<" ";
    }
    g<<endl;
    return 0;
}