#include <stdio.h>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;

int n,m,x,y,c,b[10],h[10],size[10],z,p,q,d[10];
vector <int> a[50010];
vector <int> cost[50010];

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	int i,j;
	for (i=1; i<=m; ++i)
	{
		scanf("%d%d%d",&x,&y,&c);
		a[x].push_back(y);
		cost[x].push_back(c);
		size[x]=a[x].size();
	}
	b[1]=0;
	for (i=2; i<=n; ++i) { b[i]=inf;h[i]=i;d[i]=i; }
	h[1]=1;
	d[1]=1;
	z=n;
	for (i=1; i<=n; ++i)
	{
		for (j=0; j<size[h[1]]; ++j)
			if (b[h[1]]+cost[h[1]][j]<b[a[h[1]][j]]) 
			{
				b[a[h[1]][j]]=b[h[1]]+cost[h[1]][j];
				p=d[a[h[1]][j]];
				q=1;
				while (q==1 && p>1)
				{
					q=0;
					if (b[h[p]]<b[h[p/2]])
					{
						q=1;
						x=h[p];
						h[p]=h[p/2];
						h[p/2]=x;

						x=d[h[p]];
						d[h[p]]=d[h[p/2]];
						d[h[p/2]]=x;

						p=p/2;
					}
				}
			}
		d[h[1]]=z;
		h[1]=h[z--];
		p=1;
		q=1;
		while (q==1)
		{
			y=1;
			if (b[h[p*2+1]]<b[h[p*2]]) y=2;
			q=0;
			if (b[h[p]]>b[h[p*2]] && z>=p*2 && y==1)
			{
				q=1;
				x=h[p];
				h[p]=h[p*2];
				h[p*2]=x;
				p=p*2;
			}
			if (b[h[p]]>b[h[p*2+1]] && z>=p*2+1 && q==0 && y==2)
			{
				q=1;
				x=h[p];
				h[p]=h[p*2+1];
				h[p*2+1]=x;
				p=p*2+1;
			}
		}
	}
	for (i=2; i<=n; ++i)
	{
		if (b[i]==inf) { printf("0 "); continue; }
		printf("%d ",b[i]);
	}
	return 0;
}