#include <stdio.h>
#define dim 50100
#define inf 1000000000

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

inline int father(int x)
{
	return x>>1;
}

inline int left_son(int x)
{
	return x<<1;
}

inline int right_son(int x)
{
	return (x<<1)+1;
}

inline int minim()
{
	return h[1];
}

void sift(int x)
{
	int son, t;
	do
	{	
		son=0;
		if (left_son(x)<=k) son=left_son(x);
		if (right_son(x)<=k && d[h[left_son(x)]]>d[h[right_son(x)]]) son=right_son(x);
		if (d[h[x]]>d[h[son]])
		{
			poz[h[x]]=son;
			poz[h[son]]=x;
			t=h[x];
			h[x]=h[son];
			h[son]=t;
			//poz[h[x]]=x;
			//poz[h[son]]=son;
			x=son;
		}
	}
	while (son);
}

void percolate(int x)
{
	int t;
	while (d[h[x]]<d[h[father(x)]] && father(x))
	{
		poz[h[x]]=father(x);
		poz[h[father(x)]]=x;
		t=h[x];
		h[x]=h[father(x)];
		h[father(x)]=t;
		//poz[h[x]]=x;
		//poz[h[father(x)]]=father(x);
		x=father(x);
	}
}

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

void cut_min()
{
	int t;
	t=h[1];
	h[1]=h[k];
	h[k]=t;
	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=minim();
		cut_min();
		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);
			}
	}
}

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);
		//add(p[b], a, cost);
	}
	dijkstra();
	for (i=2; i<=n; i++) printf("%d ", d[i]);
	return 0;
}