#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

int v[250010][3];
int m,n;
int a,b,cost;
int dest[50010];
void citire(){
	freopen("bellmanford.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&cost);
		v[i][0]=a;
		v[i][1]=b;
		v[i][2]=cost;
	}
}
void init(){
	dest[1]=0;
	for(int i=2;i<=n;i++)
		dest[i]=100000;



}
void ford(){
	for(int i=1;i<=n;i++)
		for(int 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(){
	freopen("bellmanford.out","w",stdout);
	for(int i=2;i<=n;i++)
		printf("%d ",dest[i]);
}
int main(){
	citire();
	init();
	ford();
	afisare();
	return 0;
	
}