#include <fstream>
using namespace std;
int n,m,c[10001][10001],a1,a2,a3,d[10001],v[10001],j,i,k,mi,ok;
int main(){
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			c[i][j]=2000000000;
	for(i=1;i<=n;i++)
		c[i][i]=0;
	for(i=1;i<=m;i++){
		f>>a1>>a2>>a3;
		c[a1][a2]=a3;}
	for(i=1;i<=n;i++)
		d[i]=c[1][i];
	v[1]=1;
	ok=1;
	while(ok){
		mi=2000000000;
		for(i=1;i<=n;i++)
			if(!v[i]&&mi>d[i]){
				mi=d[i];
				k=i;}
		if(mi!=2000000000){
			v[k]=1;
			for(i=1;i<=n;i++)
				if(!v[i]&&d[i]>d[k]+c[k][i])
					d[i]=d[k]+c[k][i];}
		else
			ok=0;}
	for(i=2;i<=n;i++){
		if(d[i]==2000000000)
			d[i]=0;
		g<<d[i]<<' ';}
	return 0;}