#include <stdio.h>

#define GRAPHSIZE 2048
#define INFINITY GRAPHSIZE*GRAPHSIZE
#define MAX(a, b) ((a > b) ? (a) : (b))

int e; /* The number of nonzero edges in the graph */
int n; /* The number of nodes in the graph */
long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */
long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */
int prev[GRAPHSIZE][GRAPHSIZE + 1]; /* prev[i] holds the nodes that could comes right before i in the shortest path from the source to i;
										prev[i][0] is the number of nodes and prev[i][1..] are the nodes */

void printD() {
	int i;

	printf("Distances:\n");
	for (i = 1; i <= n; ++i)
		printf("%10d", i);
	printf("\n");
	for (i = 1; i <= n; ++i) {
		printf("%10ld", d[i]);
	}
	printf("\n");
}

/*
 * Prints the shortest path from the source to dest.
 *
 * dijkstra(int) MUST be run at least once BEFORE
 * this is called
 */
void printPath(int dest, int depth) {
	int i, j;

	printf("-%d\n", dest);
	for (i = 1; i <= prev[dest][0]; ++i) {
		for (j = 0; j <= depth; ++j)
			printf(" |");
		printPath(prev[dest][i], depth + 1);
	}
}

void dijkstra(int s) {
	int i, k, mini;
	int visited[GRAPHSIZE];

	for (i = 1; i <= n; ++i) {
		d[i] = INFINITY;
		prev[i][0] = 0; /* no path has yet been found to i */
		visited[i] = 0; /* the i-th element has not yet been visited */
	}

	d[s] = 0;

	for (k = 1; k <= n; ++k) {
		mini = -1;
		for (i = 1; i <= n; ++i)
			if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))
				mini = i;

		visited[mini] = 1;

		for (i = 1; i <= n; ++i)
			if (dist[mini][i]) {
				if (d[mini] + dist[mini][i] < d[i]) { /* a shorter path has been found */
					d[i] = d[mini] + dist[mini][i];
					prev[i][0] = 1;
					prev[i][1] = mini;
				} else if (d[mini] + dist[mini][i] == d[i]) { /* a path of the same length has been found */
					++prev[i][0];
					prev[i][prev[i][0]] = mini;
				}
			}
	}
}

int main(int argc, char *argv[]) {
	int i, j;
	int u, v, w;

	FILE *fin = fopen("dist.txt", "r");
	fscanf(fin, "%d", &e);
	for (i = 0; i < e; ++i)
		for (j = 0; j < e; ++j)
			dist[i][j] = 0;
	n = -1;
	for (i = 0; i < e; ++i) {
		fscanf(fin, "%d%d%d", &u, &v, &w);
		dist[u][v] = w;
		n = MAX(u, MAX(v, n));
	}
	fclose(fin);

	dijkstra(1);

	printD();

	printf("\n");
	for (i = 1; i <= n; ++i) {
		printf("Path to %d:\n", i);
		printPath(i, 0);
		printf("\n");
	}

	return 0;
}