#include <stdio.h>

#define Nmax 50100
#define INF 1000000000

struct nod{
    int info,cost;
    nod *next;
};

nod *g[Nmax];

int h[Nmax],p[Nmax],c[Nmax],n,m,cnt;

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

void add(int k,int l,int c)
{
    nod *current = new nod;
    current->info=l;
    current->cost=c;
    current->next=g[k];
    g[k]=current;
}

void down(int poz)
{
    int min=poz;
    while(min<=cnt)
        {
            if( (min<<1) <=cnt)
                {
                    min=poz<<1;
                    if(min+1<=cnt)
                        if(c[h[min+1]]<c[h[min]])
                            ++min;
                }
            else
                return ;
            if(c[h[poz]]>c[h[min]])
                {
                    p[h[poz]]=min;
                    p[h[min]]=poz;
                    swap(min,poz);
                    poz=min;
                }
            else
                return ;
        }
}

void pop()
{
    h[1]=h[cnt--];
    p[h[1]]=1;
    down(1);
}

void up(int poz)
{
    int t;
    if(poz>1)
        {
            t=poz>>1;
            if(c[h[t]]>c[h[poz]])
                {
                    p[h[t]]=poz;
                    p[h[poz]]=t;
                    swap(t,poz);
                    up(t);
                }
        }
}

int main()
{
    int i,x,y,co;

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

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;++i)
        {
            scanf("%d%d%d",&x,&y,&co);
            add(x,y,co);
        }

    for(i=1;i<=n;++i)
        {
            p[i]=-1;
            c[i]=INF;
        }

    c[1]=0;
    p[1]=1;
    h[++cnt]=1;

    while(cnt)
        {
            int min=h[1];
            pop();

            nod *current=g[min];

            while(current)
                {
                    if(c[current->info]>c[min]+current->cost)
                        {
                            c[current->info]=c[min]+current->cost;

                            if(p[current->info]==-1)
                                {
                                    h[++cnt]=current->info;
                                    p[h[cnt]]=cnt;
                                    up(cnt);
                                }
                            else
                                {
                                    up(p[current->info]);
                                }
                        }
                    current=current->next;
                }
        }

    for(i=2;i<=n;++i)
        if(c[i]!=INF)
            printf("%d ",c[i]);
        else
            printf("0 ");
    return 0;
}