#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
long v[250010][3];
long m,n;
long a,b,cost;
long dest[50010];
void citire(){
	f>>n>>m;
	for(long i=1;i<=m;i++){
		f>>a>>b>>cost;
		v[i][0]=a;
		v[i][1]=b;
		v[i][2]=cost;
	}
}
void init(){
	dest[1]=0;
	for(long i=2;i<=n;i++)
		dest[i]=100000;



}
void ford(){
	for(long i=1;i<=n;i++)
		for(long j=1;j<=m;j++){
			a=v[j][0];
			b=v[j][1];
			cost=v[j][2];
			if(dest[a]+cost<dest[b])
				dest[b]=dest[a]+cost;
		}


}
void afisare(){
	for(int i=2;i<=n;i++)
		g<<dest[i]<<' ';
}
int main(){
	citire();
	init();
	ford();
	afisare();
	return 0;
	
}