#include <cstdio>
#define DIM 1005
const int INF = 1<<30;

int a[DIM][DIM], n, m, d[DIM], v[DIM];

int smallest()
{
	int min = INF, ibun;
	for (int i = 1 ; i <= n; i++)
		if (!v[i])
			if (d[i] < min)
				min = d[i], ibun = i;

	return ibun;
}

int gata()
{
	for (int i = 1; i <= n; i++)
		if (!v[i])
			return 0;

	return 1;
}

int main()
{
	FILE *f = fopen("dijkstra.in", "r");
	fscanf(f, "%d%d", &n, &m);
	if (n > DIM)
	{
		printf("CACA!\n");return 0;
	}
	int i, x, y, j;
	for (i = 1; i <= n; d[i] = INF,  i++)
		for (j = 1; j <= n; j++)
			a[i][j] = INF;

	for (i = 1; i <= m; i++)
	{
		fscanf(f, "%d%d", &x, &y);
		fscanf(f, "%d", &a[x][y]);
		//a[y][x] = a[x][y];
	}

	fclose(f);
/*	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
			if (a[i][j] != INF)
				printf("%3d", a[i][j]);
			else
				printf("  X");

		printf("\n");
	}
*/

	d[1] = 0, v[1] = 0;

	while (!gata())
	{
		i = smallest();
		for (j = 1; j <= n; j++)
			if (!v[j] && a[i][j] != INF)
				if (d[i] + a[i][j] < d[j])
				{
					d[j] = d[i] + a[i][j];

				}


		v[i] = 1;
	}

	f = fopen("dijkstra.out", "w");
	for (i = 2; i <= n; i++)
		fprintf(f, "%d ", (d[i] == INF)? 0 : d[i]);

	fclose(f);
	return 0;
}