#include <stdio.h>
#define DIM 50005
#define INF 1234567891

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 (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 min=nod;
	if (2*nod<=l) if (c[h[nod*2]]<c[h[min]]) min=2*nod;
	if (2*nod+1<=l) if (c[h[2*nod+1]]<c[h[min]]) min=2*nod+1;
	if (min!=nod)
		{
		swap(h[nod], h[min]);
		swap(poz[h[nod]],poz[h[min]]);
        downheap(min);
		}
}

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;
}