#include <cstdio>
#include <climits>
#define INF 32000
#define DIM 10005
short a[DIM][DIM];
int v[DIM], d[DIM], n, m;

int main()
{
	int i, j, x, y;

	FILE *f = fopen("dijkstra.in", "r");
	fscanf(f, "%d%d", &n, &m);
	for (i = 1; i <= n; i++)
	{
		d[i] = INF;
		for (j = 1; j <= n; j++)
			a[i][j] = INF;
	}


	for (i = 1; i <= n; i++)
		fscanf(f, "%d%d", &x, &y), fscanf(f, "%hd", &a[x][y]), a[y][x] = a[x][y];

	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;
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
			if (a[i][j] < d[j])
				if (!v[j])
					d[j] = d[i] + a[i][j];

		v[i] = 1;
	}

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

	fclose(f);

	return 0;
}