#include <stdio.h>
#include <stdlib.h>
#include <values.h>
#define Nmax 50001

struct graf {int nod, cost; graf * next ;} * g[Nmax];
int n, m, i, x, y, z, nrH, dist;
int *d, poz[Nmax], h[Nmax];

void dijkstra(int, int *);

int main()
{
	freopen("dijkstra.in", "r", stdin);
	scanf("%d %d\n", &n, &m);
	d=(int *)calloc(n+2, sizeof(int));
	for (; m; m--)
	{
		scanf("%d %d %d\n", &x, &y, &z);
		graf * q = new graf;
		q->nod=y; q->cost=z; q->next=g[x]; g[x]=q;
		q= new graf;
		q->nod=x; q->cost=z; q->next=g[y]; g[y]=q;
	}
	dijkstra(1,d);
	freopen("dijkstra.out", "w", stdout);
	for (i=2; i<=n; i++) printf("%d ", d[i]==MAXINT?0:d[i]);
	fclose(stdout);
	return 0;
}

void heapup(int);
void heapdown(int);

void dijkstra(int x, int * d)
{
	for (i=2; i<=n; i++) d[i]=MAXINT;
	h[++nrH]=1;
	poz[1]=1;
	while (nrH)
	{
		x=h[1]; dist=d[x];
		if (nrH>1)
		{
			poz[x]=0;
			poz[h[nrH]]=1;
			h[1]=h[nrH--];
			heapdown(1);
		}
		else
		{
			nrH--;
			poz[h[1]]=0;
		}
		for (graf * p=g[x]; p; p=p->next)
		{
			if (d[p->nod] > dist + p->cost)
			{
				d[p->nod] = dist + p->cost;
				if (poz[p->nod]) heapup(poz[p->nod]);
				else
				{
					h[++nrH]=p->nod;
					poz[p->nod]=nrH;
					heapup(nrH);
				}
			}
		}
	}
}

void heapup(int loc)
{
	if (loc==1) return;
	int tata = loc>>1, temp;
	if (d[h[loc]] < d[h[tata]])
	{
		poz[h[loc]]=tata;
		poz[h[tata]]=loc;
		temp = h[tata];
		h[tata]=h[loc];
		h[loc]=temp;
		heapup(tata);
	}
}

void heapdown(int loc)
{
	int fiu, temp;

	if (loc<<1 <= nrH)
	{
		fiu=loc<<1;
		if (fiu+1<=nrH && d[h[fiu+1]]<d[h[fiu]])
			fiu++;
	}
	else return;

	if (d[h[loc]]<d[h[fiu]]) return;

	poz[h[loc]]=fiu;
	poz[h[fiu]]=loc;
	temp=h[loc];
	h[loc]=h[fiu];
	h[fiu]=temp;
	heapdown(fiu);
}