#include <iostream>
#include <fstream>
#define MAX 50001
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int INF=1<<30;

typedef struct Nod{
    int nod, cost;
    Nod *next;
}*pNod;

int n, m; ///dimensiunile grafului
pNod g[MAX]; ///vector de adiacenta
int d[MAX], h[MAX], poz[MAX];

void add(int where, int what, int cost){
    pNod p;
    p=new Nod;
    p->nod=what;
    p->cost=cost;
    p->next=g[where];
    g[where]=p;
}

void read(){
    fin>>n>>m;
    for(int i=1; i<=m; i++){
        int x, y, z;
        fin>>x>>y>>z;
        add(x, y, z);
    }
}

void swap(int x, int y){
    int t=h[x];
    h[x]=h[y];
    h[y]=t;
}

void upheap(int what){
    int tata;
    while(what>1){
        tata=what>>1;
        if(d[h[tata]]>d[h[what]]){
            poz[h[what]]=tata;
            poz[h[tata]]=what;
            swap(tata, what);
            what=tata;
        }
        else what=1;
    }
}

int k;

void downheap(int what){
    int f;
    while(what<=k){
        f=what;
        if((what<<1)<=k){
            f=what<<1;
            if(f+1<=k && d[h[f+1]]<d[h[f]])
                ++f;
        }
        else return;
        if(d[h[what]]>d[h[f]]){
            poz[h[what]]=f;
            poz[h[f]]=what;
            swap(f, what);
            what=f;
        }
        else return;
    }
}

void dijkstraHeap(){
    for(int i=2; i<=n; i++){
        d[i]=INF;
        poz[i]=-1;
    }
    poz[1]=1;
    h[++k]=1;
    while(k){
        int min=h[1];
        swap(1, k);
        poz[h[1]]=1;
        --k;
        downheap(1);
        pNod p=g[min];

        while(p){
            if(d[p->nod]>d[min]+p->cost){
                d[p->nod]=d[min]+p->cost;
                if(poz[p->nod]!=-1)
                    upheap(poz[p->nod]);
                else{
                    h[++k]=p->nod;
                    poz[h[k]]=k;
                    upheap(k);
                }
            }
        p=p->next;
        }
    }
}

int main()
{
    read();
    cout<<INF;
    dijkstraHeap();
    for(int i=2; i<=n; i++)
        fout<<d[i]<<' ';
}