#include<cstdio>
#include<climits>
#include <cmath>
struct nheap
{
    int dmin,k;
} heap[100001],haux;
struct nod
{
    int inf,c;
    nod *next;
}*lv[100001],*p,*q;
int viz[100001],idx[100001],rasp[100001],aux;
FILE *fin=fopen("dijkstra.in","r"),*fout=fopen("dijkstra.out","w");
int main()
{
    int n,i,j,dmin,k,x,y,cost,m,s,nodc,f;
    s=1;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1; i<=n; i++)
    {
        idx[i]=-1;
        rasp[i]=0;
    }
    rasp[s]=0;
    for(i=1; i<=m; i++)
    {
        fscanf(fin,"%d%d%d",&x,&y,&cost);
        p=new nod;
        p->inf=y;
        p->c=cost;
        p->next=lv[x];
        lv[x]=p;
    }
    viz[s]=1;
    int nh=0;
    for(nod *p=lv[s]; p; p=p->next)
    {

        nh++;
        idx[p->inf]=nh;
        heap[nh].dmin=p->c;
        heap[nh].k=p->inf;
        nodc=nh;
        while(nodc>1 && heap[nodc].dmin<heap[nodc/2].dmin)
        {
            haux=heap[nodc];
            heap[nodc]=heap[nodc/2];
            heap[nodc/2]=haux;
            aux=idx[heap[nodc].k];
            idx[heap[nodc].k]=idx[heap[nodc/2].k];
            idx[heap[nodc/2].k]=aux;
            nodc/=2;
        }
    }
    int kmin;
    while(nh)
    {
        kmin=heap[1].k;
        dmin=heap[1].dmin;
        rasp[kmin]=dmin;
        viz[kmin]=1;
        heap[1]=heap[nh--];
        idx[kmin]=-1;
        idx[heap[1].k]=1;
        nodc=1;
        while(1)
        {
            f=2*nodc;
            if(f>nh) break;
            if(f+1<=nh&&heap[f+1].dmin<heap[f].dmin) f++;
            if(heap[nodc].dmin<=heap[f].dmin) break;
            haux=heap[nodc];
            heap[nodc]=heap[f];
            heap[f]=haux;
            aux=idx[heap[nodc].k];
            idx[heap[nodc].k]=idx[heap[f].k];
            idx[heap[f].k]=aux;
            nodc=f;
        }
        for(p=lv[kmin]; p; p=p->next)
            if(!viz[p->inf])
            {
                nodc=0;
                if(idx[p->inf]==-1)
                {
                    nh++;
                    heap[nh].dmin=dmin+p->c;
                    heap[nh].k=p->inf;
                    idx[p->inf]=nh;
                    nodc=nh;
                }
                else if(dmin+p->c<heap[idx[p->inf]].dmin)
                {
                    heap[idx[p->inf]].dmin=dmin+p->c;
                    nodc=idx[p->inf];
                }
                while(nodc>1 && heap[nodc].dmin<heap[nodc/2].dmin)
                {
                    haux=heap[nodc];
                    heap[nodc]=heap[nodc/2];
                    heap[nodc/2]=haux;
                    aux=idx[heap[nodc].k];
                    idx[heap[nodc].k]=idx[heap[nodc/2].k];
                    idx[heap[nodc/2].k]=aux;
                    nodc/=2;
                }
            }
    }
    for(i=2; i<=n; i++) fprintf(fout,"%d ",rasp[i]);
    return 0;
}