using namespace std;
#include<cstdio>
#include<fstream>
#include<iostream>
#define MAX 50005
#define INFINIT 1073741823
#define heap H
#define nh nH
inline int father(int k){
    return k/2;}
inline int left_son(int k){
    return k*2;}
inline int right_son(int k){
    return k*2+1;}
struct nod{
    int capat,cost;
    nod *next;
};

nod *G[MAX];
int H[MAX],d[MAX],v[MAX],nH,n,t[MAX],poz[MAX];

void addArc(int x,int y,int c)
{
    nod *p=new nod;
    p->cost=c;
    p->capat=y;
    p->next=G[x];
    G[x]=p;
}

void cerne(int k)
{
    int son;
    do
    {
        son=0;
        if(left_son(k)<=nh)
        {
            son=left_son(k);
            if(right_son(k)<=nh && d[H[right_son(k)]]<d[H[son]])
                son=right_son(k);
            if(d[H[son]]>=d[H[k]])
                son=0;
        }
        if(son)
        {
            swap(H[son],H[k]);
            swap(poz[H[son]],poz[H[k]]);
            k=son;
        }
    }while(son);
}

void promoveaza(int k)
{
    while( (k>1) && (d[H[father(k)]]> d[H[k]]) )
    {
        swap(H[father(k)],H[k]);
        swap(poz[H[father(k)]],poz[H[k]]);
        k=father(k);
    }
}

void init(int sursa)
{
    int i;
    for(i=0;i<=n;i++)
        v[i]=0,d[i]=INFINIT,t[i]=-1 ,H[i]=i,poz[i]=i;//initializez vectorii
    nH=n;
    v[sursa]=1,d[sursa]=0,t[sursa]=0;
    H[sursa]=H[nH--];//scot primu vf din heap;
    poz[H[sursa]]=sursa;
    cerne(sursa);
    for(nod *p=G[sursa]; p ; p=p->next)//actualizez d[vecin] si t[vecin] pt vecinii primului vf
    {
        d[p->capat]=p->cost;
        t[p->capat]=sursa;
        promoveaza(poz[p->capat]);
    }
}

void dijkstra(int sursa)
{
    init(sursa);
    for(int qq=1;qq<n;qq++)//fac n-1 pasi (pt toate vf);
    {
        int pmin=H[1];
        if(d[pmin]==INFINIT)
            break;
        v[pmin]=1;//scot vf curent din heap si il marchez ca vizitat;
        H[1]=H[nH--];
        poz[H[1]]=1;
        cerne(1);
        for(nod *p=G[pmin] ; p ; p=p->next)//actualizez vecinii nodului curent
            if((d[pmin] + p->cost) < d[p->capat])
            {
                t[p->capat]=pmin;
                d[p->capat]=d[pmin]+p->cost;
                promoveaza(poz[p->capat]);
            }
    }
}

int main()
{
    int i,m;
    freopen("dijkstra.in","r", stdin);
    freopen("dijkstra.out","w", stdout);
    scanf("%d %d", &n, &m);
    for(i=1;i<=m;i++)
    {
        int x,y,c;
        scanf("%d %d %d", &x, &y, &c);
        addArc(x,y,c);
    }
    dijkstra(1);
    for(i=2;i<=n;i++)
    {
        if(d[i]!=INFINIT)
            printf("%d ", d[i]);
        else
            printf("0 ");
    }
    return 0;
}