#include<stdio.h>
#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");

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

void dijkstra()
{
	long k;
	for(k=2;k<=n;++k)
		d[k]=INF;
	
	d[1]=0;
	q.push(1);
	v[1]=0;

	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();
	long i;
	for(i=2;i<=n; ++i)
		if(d[i]==INF) fprintf(g,"0 ");
	    else fprintf(g,"%ld ",d[i]);
		
	fprintf(g,"\n");
	fclose(g);
	return 0;
}