#include<fstream>
#define maxn 50001
using namespace std;
//vector <int> a[maxn];
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int a[5001][5001],q[5001],inc,sf,d[50000],x,y,m,i,c,n;
int main()
{
	fin>>n>>m;
	for (i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		//a(x) push.back(y);
		//a(y) push.back(x); 
		a[x][y]=c;
	}
	q[1]=1;
	for (i=1;i<=n;i++)
		{
			d[i]=1001;
		}
	d[1] = 0;
	inc=1;sf=1;
	while (inc<=sf)
	{
		x=q[inc]; inc++;
		for (i=1;i<=n;i++)
			if (a[x][i]!=0) 
				if(d[i]>d[x]+a[x][i]) 
				{
					d[i]=d[x]+a[x][i]; 
					sf++; 
					q[sf]=i;
				}
	}
	for (i=2;i<=n;i++)
		fout<<d[i]<<' ';
	fout.close();
	return 0;
}