#include<fstream>
#include<vector>
using namespace std;
# define nmax 50001
# define inf 250000001
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector <int> d[nmax],v[nmax];
int n,m;
long long dist[nmax];
bool uz[nmax];
void citire()
{
	f>>n>>m;int i,j,dis,p;
	for(p=1;p<=m;p++)
	{
		f>>i>>j>>dis;
		v[i].push_back(j);
		d[i].push_back(dis);
	}
}
int minim()
{
	int i,q=inf,poz=0;
	for(i=1;i<=n;i++)
	{
		if(!uz[i] && dist[i]<q)
		{
			q=dist[i];poz=i;
		}
	}
	return poz;
}
int main()
{
	citire();int l,i,poz;
	for(i=1;i<=n;i++)
		dist[i]=inf;
	l=v[1].size();uz[1]=1;dist[1]=0;
	for(i=0;i<l;i++)
	{
		dist[v[1][i]]=d[1][i];
	}
	poz=minim();
	while(poz)
	{
		l=v[poz].size();
		for(i=0;i<l;i++)
			if(dist[v[poz][i]]>dist[poz]+d[poz][i])
			{
				dist[v[poz][i]]=dist[poz]+d[poz][i];
			}
		uz[poz]=1;
		poz=minim();
	}
	for(i=2;i<=n;i++)
		if(dist[i]!=inf) g<<dist[i]<<" ";
		else g<<0<<" ";
}