#include<fstream>
#define maxn 999999999
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
long long int d[50001];
unsigned int n,m;
struct muchie{
	unsigned int x,y,c;
};
muchie v[50001];
void bell(int r){
	d[r]=0;
	int ok=1;
	for(int nr=1;nr<n && ok;++nr){
		ok=0;
		for(int i=1;i<=m;++i){
			int xx=v[i].x;
			int yy=v[i].y;
			int cost=v[i].c;
			if(d[yy]>d[xx]+cost)
				d[yy]=d[xx]+cost,ok=1;
		}
	}
}

void citire(){
	f>>n>>m;
	for(int i=1;i<=n;++i)
		d[i]=maxn;
	for(int i=1;i<=m;++i){
		f>>v[i].x>>v[i].y>>v[i].c;
	}
}
int main(){
	citire();
	bell(1);
	for(int i=2;i<=n;++i)
		if(d[i]!=maxn)
		g<<d[i]<<" ";
		else
			g<<0<<" ";
	return 0;
}