#include<fstream>
#include<cmath>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define inf 2000000000
int a[1000][1000], viz[1000];

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 d[1000], i, k, ok, min;
	for( i = 0; i < n; i++ )
		d[i] = a[x][i];
	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] != inf && a[k][i] != inf )
					if( d[k] + a[k][i] < d[i] && viz[i] == 0 )
						d[i] = d[k] + a[k][i];
		}
		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;
}