#include <stdio.h>
#define DIM 50005
#define INF 1<<31-1

struct nod {int x,ct;
			nod *urm;} *lst[DIM];
int c[DIM],h[DIM],poz[DIM];
int n,m,l;

void add (int a,int b,int c)
{
	nod *p=new nod;
	p->x=b;
	p->ct=c;
	p->urm=lst[a];
	lst[a]=p;
}

void read ()
{
	int i,x,y,z;
	scanf ("%d%d",&n,&m);
	for (i=1; i<=m; ++i)
	{
		scanf ("%d%d%d",&x,&y,&z);
		add (x,y,z);
	}
}

void init ()
{
	int i;
	poz[1]=1;
	for (i=2; i<=n; ++i)
		c[i]=INF;
}

void swap (int &a,int &b)
{
	int aux=a;
	a=b;
	b=aux;
}

void upheap (int nod)
{
	if (nod>=1) return;
	if (h[nod]>h[nod/2] && c[h[nod]]>c[h[nod/2]])
		{
			swap(h[nod],h[nod/2]);
			swap(poz[h[nod]],poz[h[nod/2]]);
		}
	upheap(nod/2);
}

void downheap (int nod)
{
	int son;
	do
	{
		son=0;
		if (2*nod<=l)
		{
			son=2*nod;
			if (2*nod+1<=l && c[h[2*nod+1]]<c[h[2*nod]])
                son=2*nod+1;
            if (c[h[son]]>=c[h[nod]])
                son=0;
        }
        if (son)
        {
            swap (poz[h[nod]],poz[h[son]]);
            swap (h[nod],h[son]);
            nod=son;
        }
    }
    while (son);
}

void solve ()
{
    nod *p;
    int i,min;
    for (h[++l]=1; l; )
    {
        min=h[1];
        h[1]=h[l--];
        poz[h[1]]=1;
        downheap (1);
        for (p=lst[min]; p; p=p->urm)
            if (c[p->x]>c[min]+p->ct)
            {
                c[p->x]=c[min]+p->ct;
                if (poz[p->x])
                    upheap (poz[p->x]);
                else
                {
                    poz[h[++l]=p->x]=l;
                    upheap (l);
                }
            }
    }
}

void print ()
{
    int i;
    for (i=2; i<=n; ++i)
        if (c[i]!=INF)
            printf ("%d ",c[i]);
        else
            printf ("0 ");
}

int main ()
{
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);
    read ();
    init ();
    solve ();
    print ();
    return 0;
}