#include<fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define inf 1000000
int a[100][100], viz[100];
/*void citire( int &n, int &x ){
	int i, j;
	f >> n >> x;
	x--;
	for( i = 0; i < n; i++ )
		for( j = 0; j < n; j++ ){
			f >> a[i][j];
			if( i != j && a[i][j] == 0 )
				a[i][j] = inf;
		}
}*/

void citire( int &n ){
	int i, j, x, y, c, m;
	f >> n >> m;
	for( i = 0; i < m; i++ ){
		f >> x >> y >> c;
		x--; y--;
		a[x][y] = c;
	}
	for( i = 0; i < n; i++ )
		for( j = 0; j < n; j++ )
			if( a[i][j] == 0 )
				a[i][j] = inf;
		
}

void dijkstra(int n, int x){
	int tata[100], d[100], i, k, ok, min;
	for( i = 0; i < n; i++ ){
		tata[i] = x;
		d[i] = a[x][i];
	}
	tata [x] = 0;
	viz[x] = 1;
	ok = 1;
	while( ok == 1 ){
		min = inf;
		for( i = 0; i < n; i++ )
			if( viz[i] == 0 && d[i] < min ){
				min = d[i];
				k = i;
			}
		if( min != inf ){
			viz[k] = 1;
			for( i = 0; i < n; i++ )
				if( d[k] + a[k][i] < d[i] ){
					d[i] = d[k] + a[k][i];
					tata[i] = k;
				}
		}
		else ok = 0;
	}
	/*for( i = 0; i < n; i++ )
		g << tata[i] + 1 << " ";
	g << endl;*/
	
	for( i = 1; i < n; i++ )
		if (d[i] == inf)
			g << 0 << " ";
		else
			g << d[i] << " ";
}
int main(){
	int n, x;
	citire(n);
	x = 0;
	dijkstra(n, x);
	return 0;
}