#include <iostream>
#include <fstream>
#define inf 1<<30
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){
    poz[H[a]]=b;
    poz[H[b]]=a;
    swap(H[a],H[b]);
}
void upheap(int w){
    int tata;
    while(w>1){
        tata=w>>1;
        if(D[H[tata]]>D[H[w]]){
            swapheap(tata,w);
            w=tata;
        }else{
            w=0;
        }
    }
}
void downheap(int w){
    int f;
    while(w<=k){
        f=w<<1;
        if(f<=k){
            if(D[H[f]]>D[H[f+1]] && f+1<=k){
                f++;
            }
            if(D[H[f]]<D[H[w]]){
                swapheap(f,w);
                w=f;
            }else{
                return;
            }
        }else{
            return;
        }
    }
}
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++){
        if(D[i]!=inf){
            g<<D[i]<<" ";
        }else{
            g<<0<<" ";
        }
    }
    g<<endl;
    return 0;
}