# include <stdio.h>
# include <stdlib.h>
# define datain "dijkstra.in"
# define dataout "dijkstra.out"
# define inf 1 << 14
typedef struct nod {
	unsigned int nod;
	int cost;
	struct nod *leg;
	} NOD;
typedef struct graf {
	unsigned int n;
	NOD **v;
	} GRAF;
void initG (GRAF **g,unsigned int n) {
	(*g)->n = n;
	(*g)->v = (NOD **) calloc ((n+1), sizeof (NOD *));
}
void addArc (GRAF **g, unsigned int x, unsigned int y, int z) {
	NOD *new = (NOD *) malloc (sizeof (NOD));
	new->nod = y;
	new->cost = z;
	new->leg = (*g)->v[x];
	(*g)->v[x] = new;
}
void afis (GRAF g) {
	int i = 0;
	NOD *p = NULL;
	for (i = 1;i <= g.n; i++) {
		printf ("Nodul : %d ", i);
		p = g.v[i];
		while (p != NULL) {
			printf ("Vecin %u - Cost %d;  ", p->nod, p->cost);
			p = p->leg;
		}
		printf ("\n");
	}
}
void citire (GRAF **g) {
	FILE *f = fopen (datain, "rt");
	unsigned int n, x, y, i = 0;
	long m;int z;
	fscanf (f, "%u%ld", &n, &m);
	initG (g, n);
	for (i = 0; i < m; i++) {
		fscanf (f, "%u%u%d", &x, &y, &z);
		addArc (g, x, y, z);
	}
	fclose (f);
}
unsigned int dist_min (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 = 0, j = 0, u = 0, v = 0;
	for (i = 2; i <= g.n; i++)
		d[i] = inf;
	for (i = 1; i <= g.n - 1; i++) {
		u = dist_min (g, d, s);
		s[u] = 1;
		NOD *p = g.v[u];       
		while (p != NULL) {
			if ( d[p->nod] > d[u] + p->cost)
				d[p->nod] = d[u] + p->cost;
			p = p->leg;
		}		
	 }
	FILE *f = fopen (dataout, "wt");
	for (i = 2; i <= g.n; i++) {
	if (d[i] == inf)
		d[i] = 0;
		fprintf (f, "%ld ", d[i]);
		printf ("%ld ", d[i]);
	}
	fclose (f);
}
int main (void) {
	GRAF *g = (GRAF *) malloc (sizeof (GRAF));
	citire (&g);
//	afis (*g);
//	printf ("\n");
	dijkstra (*g);
	return 0;
}