#include <iostream>
#include <fstream>
using namespace std;
#define lmax 50001
#define infinit 1<<30
int n,m,i,j,h[lmax],poz[lmax],dist[lmax],k,x,pos;
struct graf{
    int nod,cost;
    graf *next;
};
graf *a[lmax];
void add(int unde,int care, int cost){
    graf *q = new graf;
    q->nod=care;
    q->cost=cost;
    q->next=a[unde];
    a[unde]=q;
}
void citire(){
    ifstream f("dijkstra.in");
    int a,b,c;
    f>>n>>m;

    for(i=0; i<m; i++)
    {
        f>>a>>b>>c;
        add(a,b,c);
    }
}
void swap(int x,int y){
    int t=h[x];
    h[x]=h[y];
    h[y]=t;
}
void downheap(int care){
    int f;
    while(care<=k){
        f=care;
        if((care<<1)<=k)
            f=care<<1;
                if(f+1<k&&dist[h[f+1]]<dist[h[f]])
                    f++;
        else return;
        if(dist[h[care]]>dist[h[f]]){
            poz[h[care]]=f;
            poz[h[f]]=care;
            swap(care,f);
            care=f;
        }
        else return;
    }
}
void upheap(int care)
{
    int tata;
    while(care>1){
        tata=care>>1;
        if(dist[h[tata]]>dist[h[care]]){
            poz[h[tata]]=care;
            poz[h[care]]=tata;
            swap(care,tata);
            care=tata;
        }
        else
            care=1;
    }
}
int main(){
    int min,pmin;
    ofstream g("dijkstra.out");
    citire();
    for(i=2;i<=n;i++)
        dist[i]=infinit,poz[i]=-1;
    poz[1]=1;
    k=1;
    h[k]=1;
    while(k){
        min=h[1];
        swap(1,k);
        poz[h[1]]=1;
        k--;
        downheap(1);
        graf *q=a[min];
        while(q){
            if(dist[q->nod]>dist[min]+q->cost){
                dist[q->nod]=dist[min]+q->cost;
                if(poz[q->nod]!=-1)
                    upheap(poz[q->nod]);
                else{
                    h[++k]=q->nod;
                    poz[h[k]]=k;
                    upheap(k);
                }
            }
            q=q->next;
        }
    }
    for(i=2;i<=n;i++)
        g<<(dist[i]==infinit?0:dist[i])<<" ";
}