#include<fstream>
#include<queue>
#include<vector>
#define M 50005
#define mp make_pair
#define INF 1000000000
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

typedef vector<pair<long,long> > VI;
VI a[M];
VI::iterator it;
long m,d[M],v[M],n;
queue<long> q;

void cit()
{
	f>>n>>m;
	long i,x,y,z;
	
	for(i=1;i<=m;++i)
	{
		f>>x>>y>>z;
		a[x].push_back(mp(y,z));
	}
	
	for(i=2;i<=n;++i)
		d[i]=INF;
	
	f.close();
}

void dijkstra()
{
	q.push(1);
	v[1]=0;
	
	long k;
		
	while(!q.empty())
	{
		k=q.front();
		q.pop();
		
		v[k]=0;
		for(it=a[k].begin();it!=a[k].end();++it)
			if(d[(*it).first]>d[k]+(*it).second) {d[(*it).first]=d[k]+(*it).second;
												  if(v[(*it).first]==0) {q.push((*it).first);
																		 v[(*it).first]=1;}
												 }
	}
}

	
int main()
{
	cit();
	dijkstra();
	
	for(long i=2;i<=n; ++i)
		if(d[i]==INF) g<<0<<" "; 
	    else g<<d[i]<<" "; 

	g.close();
	return 0;
}