#include <cstdio>
using namespace std;
int st[25001],sf[25001],next[500001],dest[500001],d[500001];
int viz[25001],heap[25001],ph[25001],dist[25001],dfin[25001];
int mh,t,i,j,m,n,x,y;
void add(int x, int y)
{
    if(st[x]==0){st[x]=t;}
    else{next[sf[x]]=t;}
    dest[t]=y;
    next[t]=0;
    sf[x]=t;
}
void change(int x1, int x2)
{
    int aux;
    aux=heap[x1];
    heap[x1]=heap[x2];
    heap[x2]=aux;
    ph[heap[x1]]=x1;
    ph[heap[x2]]=x2;
}
void upheap(int nod)
{
    if(nod==1){return;}
    if(dist[heap[nod/2]]>dist[heap[nod]])
    {
        change(nod/2,nod);
        upheap(nod/2);
    }
}
void downheap(int nod)
{
    if((dist[heap[nod*2]]<dist[heap[nod*2+1]])&&(dist[heap[nod*2]]<dist[heap[nod]]))
    {
        change(nod*2,nod);
        downheap(2*nod);
    }
    if((dist[heap[nod*2+1]]<dist[heap[nod*2]])&&(dist[heap[nod*2+1]]<dist[heap[nod]]))
    {
        change(nod*2+1,nod);
        downheap(2*nod+1);
    }
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(t=1;t<=m;t++)
    {
        scanf("%d%d%d",&x,&y,&d[t]);
        add(x,y);
    }
    dist[0]=m*1001;
    dist[1]=0;
    ph[1]=1;
    heap[1]=1;
    mh=1;
    while(viz[heap[1]]==0)
    {
        viz[heap[1]]=1;
        for(j=st[heap[1]];j;j=next[j])
        {
            if(dist[dest[j]]==0)
            {
                dist[dest[j]]=dist[heap[1]]+d[j];
                mh++;
                ph[dest[j]]=mh;
                heap[mh]=dest[j];
                upheap(mh);
            }
            else
            {
                if(dist[dest[j]]>dist[heap[1]]+d[j])
                {
                    dist[dest[j]]=dist[heap[1]]+d[j];
                    upheap(ph[dest[j]]);
                }
            }
        }
        dfin[heap[1]]=dist[heap[1]];
        dist[heap[1]]=dist[0];
        downheap(1);
    }
    for(i=2;i<=n;i++)
    {
        printf("%d ",dfin[i]);
    }
return 0;
}