#include <cstdio>
using namespace std;
int st[50001],sf[50001],next[250001],dest[250001],d[250001];
int viz[50001],heap[50001],ph[50001],dist[50001],dfin[50001];
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(viz[dest[j]]==0)
            {
                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;
}