# include <stdio.h>
# include <stdlib.h>
# define datain "dijkstra.in"
# define dataout "dijkstra.out"
# define inf 16384
typedef struct graf {
	unsigned int n;
	long m;
	int **a;
	} GRAF;
void initG (GRAF **g, int n, int m) {
	int i = 1, j = 0;
	(*g)->n = n;
	(*g)->m = m;
	(*g)->a = (int **) malloc ( (n+1) * sizeof (int*));
	for (i = 0; i <= n; i++)
		(*g)->a[i] = (int*) calloc ( (n+1) , sizeof (int));
	for (i = 0; i <= n; i++)
		for (j = 0; j <= n; j++)
			if (i == j)
				(*g)->a[i][j] = 0;
				else
				(*g)->a[i][j] = inf;	
}
void readG (GRAF **g) {
	unsigned int n = 0, x = 0, y = 0, z = 0;
	long m = 0, i = 0;
	FILE *f = fopen (datain, "rt");
	char *line = (char *) malloc (20 * sizeof (char));
	fgets (line, 20, f);
	sscanf (line, "%u%ld", &n, &m);
	initG (g, n, m);
	for (i = 0; i < m; i++) {
		fgets (line, 20 ,f);
		sscanf (line, "%u%u%d", &x, &y, &z);
		(*g)->a[x][y] = z;
	}
	free (line);
	fclose (f);
}
unsigned int min_distance (GRAF g, long *d, int *s) {
	long min = inf;
	unsigned int poz_min = 1, i = 1;
	for (i = 1; i <= g.n; i++)
		if (min > d[i] && s[i] == 0) {
			min = d[i];
			poz_min = i;
		}
	return poz_min;
}
void dijkstra (GRAF g) {
	long *d = (long *) calloc (g.n + 1, sizeof (long));
	int *s = (int *) calloc (g.n + 1, sizeof (int));
	unsigned int i = 2, u = 0, v = 0;
	for (i = 2; i <= g.n; i ++)
		d[i] = inf;
	d[1] = 0;
	for (i = 1; i <= g.n-1; i++) {
		u = min_distance (g, d, s);	
		s[u] = 1;
		for (v = 1; v <= g.n; v++)
			if (!s[v] && g.a[u][v] && d[u] != inf && d[u] + g.a[u][v] < d[v])
				d[v] = d[u] + g.a[u][v];
	}
	FILE *f = fopen (dataout, "wt");
	for (i = 2; i <= g.n; i++) {
		fprintf (f, "%ld ", d[i]);
	//	printf ("%ld ", d[i]);
	}
	fclose (f);
		
}
int main (void) {

	GRAF *g = (GRAF *) malloc (sizeof (GRAF));
	readG (&g);
	dijkstra (*g);
	return 0;
}