#include<fstream>
using namespace std;
#define maxn 50005
#define inf 1000000000

struct element{
    int cost,nod;
    element *next;
}*a[maxn];

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int h[maxn],d[maxn],poz[maxn],n,m,k;

void read(){
    cin>>n>>m;
    int x,y,c;
    for(int i=1; i<=m; i++){
        cin>>x>>y>>c;
        element *w= new element;
        w->cost=c;
        w->nod=y;
        w->next = a[x];
        a[x]=w;
    }
}

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(h[tata],h[what]);
            what=tata;
        } else what=1;
    }
}

void downheap(int what){
    int f;
    while(what<=k){
        f=what;
        if((what<<1)<=k){
            f=what<<1;
            if(f+1<=k)
                if(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(h[what],h[f]);
            what=f;
        }
        else return;
    }
}

void solve(){
    for(int i=2; i<=n; i++){
        poz[i]=-1;
        d[i]=inf;
    }
    poz[1]=h[++k]=1;

    while(k){
        int minim=h[1];
        swap(h[1],h[k]);
        poz[h[1]]=1;
        --k;
        element *q=a[minim];
        while(q){
            if(d[q->nod]>d[minim]+q->cost){
                d[q->nod]=d[minim]+q->cost;

                if(poz[q->nod]!=-1)
                    upheap(q->nod);
                else{
                    h[++k]=q->nod;
                    poz[h[k]]=k;
                    upheap(k);
                }
            }
            q=q->next;
        }
    }
    for(int i=2; i<=n; i++)
        if(d[i]==inf)
            cout<<0<<' ';
        else cout<<d[i]<<' ';
}

int main(){
    read();
    solve();
}