//cu heap
#include <cstdio>
#define inf 0x3f3f3f3f
#define N 50001

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

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

void down(int tata, int n)
{
    int fiu=tata<<1,t;
    if (fiu<n && C[V[fiu+1]]<C[V[fiu]]) fiu++;
    while (fiu<=n && C[V[tata]]>C[V[fiu]])
    {
        t=V[tata]; V[tata]=V[fiu]; V[fiu]=t;
        tata=fiu; fiu<<=1;
        if (fiu<n && C[V[fiu+1]]<C[V[fiu]]) fiu++;
    }
}

void up(int fiu)
{
    int tata=fiu>>1,t;
    while (tata && C[V[fiu]]<C[V[tata]])
    {
        t=V[tata]; V[tata]=V[fiu]; V[fiu]=t;
        fiu=tata; tata>>=1;
    }
}

int main()
{
	freopen("dijkstra.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->urm=L[x]; p->cost=z;
	    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;
    int k;
    for (i=n>>1; i; i--)
        down(i,n);

    for (i=n; i; i--)
    {
        min=C[V[1]];
        nod=V[1];

        for (p=L[nod]; p; p=p->urm)
            if (min+p->cost<C[p->val])
            {
                C[p->val]=min+p->cost;
                for (k=2; p->val!=V[k]; k++);
                up(k);
            }
        V[1]=V[i];
        down(1,i-1);
    }

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

    return 0;
}