#include <cstdio>
#define N 50010
#define inf 0x3f3f3f3f

typedef struct noduri
{
	int val,cost;
	noduri *urm;
} adr;

int E[N],C[N],V[N],n,m,i,j,x,y,z,nod,min;
adr *L[N],*p;

void down(int tata, int n)
{
    int fiu=tata<<1,nod=V[tata];
    if (C[V[fiu+1]]<C[V[fiu]] && fiu<n) fiu++;
    while (C[nod]>C[V[fiu]] && fiu<=n)
    {
        V[tata]=V[fiu];
        tata=fiu; fiu<<=1;
        if (C[V[fiu+1]]<C[V[fiu]] && fiu<n) fiu++;
    }
    V[tata]=nod;
}
/*
void up(int fiu)
{
    int tata=fiu>>1,nod=V[fiu];
    while (C[nod]<C[V[tata]] && tata)
    {
        V[fiu]=V[tata];
        fiu=tata; tata>>=1;
    }
    V[fiu]=nod;
}
*/
void make_heap(int n)
{
    for (int i=n>>1; i; i--) down(i,n);
}

int main()
{
	freopen("dijkstra2.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
    scanf("%d%d\n",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d%d%d\n",&x,&y,&z);
        p=new adr;
        p->val=y; p->cost=z;
        p->urm=L[x];
        L[x]=p;
    }
    for (p=L[1]; p; p=p->urm) C[p->val]=p->cost;
    for (i=2; i<=n; i++)
    {
        if (!C[i]) C[i]=inf;
        V[i]=i;
    }
    V[1]=1;

    for (i=n>>1; i; i--)
        down(i,n);
    int cn=n;
    for (i=1; i<n; i++)
    {
        min=C[V[1]];
        nod=V[1];
        E[nod]=1;

        for (p=L[nod]; p; p=p->urm)
            if (min+p->cost<C[p->val])
            {
                C[p->val]=min+p->cost;

            }
        V[1]=V[cn--];
        make_heap(cn);
        //down(1,cn);
    }

    for (i=2; i<=n; i++)
        if (C[i]<inf) printf("%d ",C[i]);
        else          printf("0 ");

    return 0;
}