#include<stdio.h>
const int nmax=50001;
const int INF=1000000000;
struct lista
{
    int inf,c;
    lista *urm;
};
lista *G[nmax];
int N,M,S,T;
int a[nmax],d[nmax],e[nmax],f[nmax],h[nmax],v[nmax],nh;
void cit()
{
    int i,x,y,c;
    lista *C[nmax];
    scanf("%d%d",&N,&M);
    S=1;
    for(i=1;i<=N;i++)
    {
        G[i]=new lista;
        G[i]->urm=NULL;
        C[i]=G[i];
    }
    for(i=1;i<=M;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        C[x]->urm=new lista;
        C[x]=C[x]->urm;
        C[x]->inf=y;
        C[x]->c=c;
        C[x]->urm=NULL;
    }
}
void inters(int &x,int &y)
{
    int aux=x;
    x=y;
    y=aux;
}
void cerne(int i)
{
    int min,l,r;
    l=2*i;
    r=2*i+1;
    if(l<=nh&&h[l]<h[i])
        min=l;
    else
        min=i;
    if(r<=nh&&h[r]<h[min])
        min=r;
    if(min!=i)
    {
        inters(h[i],h[min]);
        inters(e[i],e[min]);
        inters(f[e[i]],f[e[min]]);
        cerne(min);
    }
}
void Heap()
{
    int i;
    nh=N;
    for(i=nh/2;i>=1;i--)
        cerne(i);
}
void extrageMin()
{
    h[1]=h[nh];
    e[1]=e[nh];
    f[e[1]]=1;
    nh--;
    cerne(1);
}
void urca(int i)
{
    int p=i/2;
    if(h[i]<h[p])
    {
        inters(h[i],h[p]);
        inters(e[i],e[p]);
        inters(f[e[i]],f[e[p]]);
        urca(p);
    }
}
void relaxeaza(lista *c,int u)
{
    if(v[c->inf]==0&&h[f[c->inf]]>d[u]+c->c)
    {
        d[c->inf]=d[u]+c->c;
        h[f[c->inf]]=d[u]+c->c;
        urca(f[c->inf]);
    }
}
void dijkstra()
{
    int i,u;
    lista *c;

    for(i=1;i<=N;i++)
    {
        d[i]=h[i]=INF;
        e[i]=f[i]=i;
    }

    d[S]=h[S]=0;
    for(c=G[S]->urm;c;c=c->urm)
        d[c->inf]=h[c->inf]=c->c;

    Heap();

    for(i=1;i<=N;i++)
    {
        u=e[1];
        d[u]=h[1];
        v[u]=1;
        extrageMin();
        for(c=G[u]->urm;c;c=c->urm)
            relaxeaza(c,u);
    }
}
void scr()
{
    int i,ok=1;
    for(i=2;i<=N;i++)
		printf("%d ",d[i]);
	printf("\n");
}
int main()
{
    int i;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    cit();
    dijkstra();
    scr();
    fclose(stdout);
    return 0;
}