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

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

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();
		if (i<=n )
		{
			b[i]=inf;
			h[i]=i;
			d[i]=i;
		}
	}
	b[1]=0;
	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>>1]])
					{
						q=1;
						x=h[p];
						h[p]=h[p>>1];
						h[p>>1]=x;

						x=d[h[p]];
						d[h[p]]=d[h[p>>1]];
						d[h[p>>1]]=x;

						p=p>>1;
					}
				}
			}
		d[h[1]]=z;
		h[1]=h[z--];
		p=1;
		q=1;
		while (q==1)
		{
			y=1;
			if (z>=p*2+1 && b[h[p*2+1]]<b[h[p*2]]) y=2;
			q=0;
			if (z>=p*2 && b[h[p]]>b[h[p*2]] && y==1)
			{
				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;
			}
			if (z>=p*2+1 && b[h[p]]>b[h[p*2+1]] && q==0 && y==2)
			{
				q=1;
				x=h[p];
				h[p]=h[p*2+1];
				h[p*2+1]=x;
				
				x=d[h[p]];
				d[h[p]]=d[h[p*2+1]];
				d[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;
}