#include<cstdio>
#include<vector>
#define NMAX 50002
#define Inf 200000000
using namespace std;
int n,m,i,x,y,d[NMAX],c[300000],j;
vector<int>A[NMAX];
vector<int>cost[NMAX];
int main()
{
	freopen("dijkstra.in","rt",stdin);
	freopen("dijkstra.out","wt",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=n;i++)
		d[i]=Inf;
	d[1]=0;
	for (i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x,&y,&j);
		cost[x].push_back(j);
		A[x].push_back(y);
	}
	int ic,sc,z;
	ic=sc=1; c[ic]=1;
		while (ic<=sc)
			{
				z=c[ic];
				for (y=0;y<A[z].size();y++)
					if (d[z]+cost[z][y]<d[A[z][y]])
					{
						d[A[z][y]]=d[z]+cost[z][y];
						c[++sc]=A[z][y];
					}
				ic++;
			}
		for (i=2;i<=n;i++)
			if (d[i]!=Inf)printf("%d ",d[i]);
			else
				printf("%d ",0);
return 0;}