#include<algorithm>
using namespace std;

#define DIM 50001
#define INF 1000001

struct djk{
    int poz,val;};

struct graf{
    int nod,cost;
    graf *urm;};

int n,m,cnt,h[DIM];
djk a[DIM];
graf *lst[DIM];

inline int fath(int nod){

    return nod>>1;}

inline int lson(int nod){

    return nod<<1;}

inline int rson(int nod){

    return nod<<1+1;}

void add(int nod0,int nod1,int cost){
    graf *p=new graf;

    p->nod=nod1;
    p->cost=cost;
    p->urm=lst[nod0];
    lst[nod0]=p;}

void init(){
    int i;

    a[1].poz=h[1]=1;
    for(i=2; i<=cnt; ++i){
        a[i].poz=h[i]=i;
        a[i].val=INF;}}

void swap(int nod0,int nod1){
    int aux;

    aux=h[nod0];
    h[nod0]=h[nod1];
    a[h[nod0]].poz=nod0;
    h[nod1]=aux;
    a[h[nod1]].poz=nod1;}

void uph(int k){
    int aux;

    for(aux=h[k]; k>1&&a[h[k]].val<a[h[fath(k)]].val; k=fath(k)){
        h[k]=h[fath(k)];
        a[h[k]].poz=k;}
    h[k]=aux;
    a[h[k]].poz=k;}

void downh(int k){
    int aux,son;

    do{
        son=0;
        if(lson(k)<=cnt){
            son=lson(k);
            if(rson(k)<=cnt&&a[rson(k)].val<a[lson(k)].val)
                son=rson(k);
            if(a[h[son]].val>=a[h[k]].val)
                son=0;}
        if(son){
            swap(k,son);
            k=son;}}
    while(son);}

void upd(int k){

    if(k>1&&a[h[k]].val<a[h[fath(k)]].val)
        uph(k);
    else
        downh(k);}

void cut(int k){

    h[1]=h[cnt--];
    a[h[1]].poz=1;
    upd(1);}

void dijkstra(){
    int aux;
    graf *p;

    for(; cnt; ){
        aux=h[1];
        a[aux].poz=0;
        cut(1);
        for(p=lst[aux]; p; p=p->urm)
            if(a[aux].val+p->cost<a[p->nod].val){
                a[p->nod].val=a[aux].val+p->cost;
                if(a[p->nod].poz)
                    upd(p->nod);}}}

void solve(){
    int i,nod0,nod1,cost;

    scanf("%d%d",&n,&m);
    for(i=0; i<m; ++i){
        scanf("%d%d%d",&nod0,&nod1,&cost);
        add(nod0,nod1,cost);}
    cnt=n;
    init();
    /*for(i=1; i<=cnt; ++i)
        printf("%d ",h[i]);*/
    dijkstra();
    for(i=2; i<=n; ++i)
        if(a[i].val==INF)
            printf("0 ");
        else
            printf("%d ",a[i].val);}

int main(){

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    solve();
    return 0;}