#include <stdio.h>
#define dim 50100
#define inf 1<<30

struct nod
{
	int nr, c;
	nod *urm;
};
int n, m, d[dim], h[dim], poz[dim], k;
nod *p[dim];

void add(nod *&p, int nr, int c)
{
	nod *n1=new nod;
	n1->nr=nr;
	n1->c=c;
	n1->urm=p;
	p=n1;
}

void swap(int a, int b)
{
	int t=h[a];
	h[a]=h[b];
	h[b]=t;
}

void sift(int x)
{
	int son;
	do
	{	
		son=0;
		if ((x>>1)<=k) son=x>>1;
		if ((x>>1)+1<=k && d[h[(x>>1)]]>d[h[(x>>1)+1]]) son=(x>>1)+1;
		if (d[h[x]]>d[h[son]] && son)
		{
			poz[h[x]]=son;
			poz[h[son]]=x;
			swap(x, son);
			x=son;
		}
	}
	while (son);
}

void percolate(int x)
{
	while (d[h[x]]<d[h[(x>>1)]] && (x>>1))
	{
		poz[h[x]]=x>>1;
		poz[h[(x>>1)]]=x;
		swap(x, (x>>1));
		x=x>>1;
	}
}

void insert(int x)
{
	h[++k]=x;
	poz[h[k]]=k;
	percolate(k);
}

void cut_min()
{
	swap(1, k);
	k--;
	poz[h[1]]=1;
	sift(1);
}

void dijkstra()
{
	int i, min;
	nod *n1;
	for (i=1; i<=n; i++) d[i]=inf, poz[i]=-1;
	d[1]=0;
	poz[1]=1;
	h[++k]=1;
	while (k)
	{
		min=h[1];
		
		//cut_min();
		swap(1, k);
		poz[min]=-1;
		k--;
		if (k) 
		{
			poz[h[1]]=1;
			sift(1);
		}
		
		
		for (n1=p[min]; n1; n1=n1->urm)
			if (d[n1->nr]>d[min]+n1->c)
			{
				d[n1->nr]=d[min]+n1->c;
				if (poz[n1->nr]!=-1) percolate(poz[n1->nr]);
				else 
				{
					//insert(n1->nr);
					h[++k]=n1->nr;
					poz[h[k]]=k;
					percolate(k);
				}
			}
	}
}

int main()
{
	int a, b, cost, i;
	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", &a, &b, &cost);
		add(p[a], b, cost);
	}
	dijkstra();
	for (i=2; i<=n; i++) printf("%d ", d[i]==inf?0:d[i]);
	printf("\n");
	return 0;
}