#include<fstream>
#include<queue>
#include<vector>
#define M 50001
#define mp make_pair
#define INF 1000000000
using namespace std;
/*
FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");
*/

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()
{
	//fscanf(f,"%ld%ld",&n,&m);
	f>>n>>m;
	long i,x,y,z;
	
	for(i=1;i<=m;++i)
	{
		//fscanf(f,"%ld%ld%ld",&x,&y,&z);
		f>>x>>y>>z;
		a[x].push_back(mp(y,z));
	}
	//fclose(f);
	
	for(i=2;i<=n;++i)
		d[i]=INF;
	
	f.close();
}

void dijkstra()
{
	d[1]=0;
	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(int i=2;i<=n; ++i)
		if(d[i]==INF) g<<0<<" "; //fprintf(g,"0 ");
	    else g<<d[i]<<" "; //fprintf(g,"%ld ",d[i]);
/*		
	fprintf(g,"\n");
	fclose(g);
		*/
	g.close();
	return 0;
}