#include<iostream.h>
#include<fstream.h>
int main()
{
	int t[713][713],ut[713],s[713],n,i,l,min,d;
	int h,a,b,c,m;
	fstream f,g;
	f.open("dijkstra.in",ios::in);
	f>>n>>m;
	for (i=0;i<m;i++)
	{
		f>>a>>b>>c;
		t[a][b]=c;
	}
	for (i=1;i<=n;i++)
		{ut[i]=2000000;s[i]=2000000;}
	for (i=1;i<=n;i++)
		{ut[i]=2000000;s[i]=2000000;}
	ut[1]=2000;s[1]=0;l=1;
	for (i=1;i<n;i++)
	{
		min=2000;
		for (d=1;d<=n;d++)
			if (t[l][d]!=0)
				if (s[l]+t[l][d]<ut[d])
					ut [d]=s[l]+t[l][d];
		for (d=1;d<=n;d++)
			if (ut[d]<min) {min=ut[d];h=d;}
		if (ut[h]<s[h]) s[h]=ut[h];
		ut[h]=2000;
		l=h;
	}
	g.open("dijkstra.out",ios::out);
	for (i=2;i<=n;i++)
	{
		if (s[i]==2000000) s[i]=0;
		g<<s[i]<<" ";
	}
	g<<'\n';
	g.close();
}