#include <fstream>
#define N 10000
#define MARE 100000000

using namespace std;

ifstream fi ("dijkstra.in");
ofstream fo ("dijkstra.out");

int a[N][N], d[N], km, i, j, l, c, n, m;
bool sel[N];

void Dijkstra (int s) {
	int min, dn, jmin;
/*	for (i = 1; i <= n; i++) {
		d[i] = MARE;
		if (a[s][i] != 0)
			d[i] = a[s][i];
	}*/
	for(i=1; i<=n; i++)
		d[i]=a[s][i];
	d[s] = 0; sel[s] = true;
	for (i = 2; i <= n; i++) {
		min = MARE;
		for (j = 1; j <= n; j++)
			if (!sel[j] and min > d[j]) {
					min = d[j]; jmin = j;
			}
		sel[jmin] = true;
		for (j = 1; j <= n; j++)
			if(!sel[j]) {
				dn = d[jmin] + a[jmin][j];
				if (d[j] > dn)
					d[j] = dn;
			}
	}
}

int main () {
	fi >> n >> m;
	for (i = 1; i <= m; i++) {
		fi >> l >> c >> km;
		a[l][c] = km;
	}
	for (l = 1; l <= n; l++)
		for (c = 1; c <= n; c++)
			if (a[l][c] == 0)
			a[l][c] = MARE;
		Dijkstra(1);
	for (i = 2; i <= n; i++)
		fo << d[i] << ' ';
/*	fo << '\n';
	for (l = 1; l <= n; l++) {
		for (c = 1; c <= n; c++)
			fo << a[l][c] << ' ';
		fo << '\n';
	}*/
	return 0;
}