#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct arcType {
	int nod;
	int cost;
} arc;

typedef struct vectArc {
	arc* data;
	int size;
	int capacity;
} vectArc;
typedef vectArc* vector;

vector vec_new(int initCap) {
	if(initCap < 10) {
		initCap = 10;
	}
	vector vect = (vector)malloc(sizeof(vectArc));
	vect->capacity = initCap;
	vect->size = 0;
	vect->data = (arc*)malloc(vect->capacity * sizeof(arc));
	return vect;
}

void vec_free(vector vect) {
	free(vect->data);
	free(vect);
}

void vec_push_back(vector vect, int val, int c) {
	if(vect->size == vect->capacity) {
		vect->capacity = 2 * vect->capacity;
		arc* newData = (arc*)malloc(vect->capacity * sizeof(arc));
		memcpy(newData, vect->data, vect->size * sizeof(arc));
		free(vect->data);
		vect->data = newData;
	}
	vect->data[vect->size].nod = val;
	vect->data[vect->size].cost = c;
	vect->size++;
}

void swap(arc** a, arc** b) {
	arc* temp = *a;
	*a = *b;
	*b = temp;
}

void delete(arc** h, int pos, int* last, int* p) {
	swap(&h[pos], &h[*last]);
	p[h[*last]->nod] = 0;
	p[h[pos]->nod] = pos;
	free(h[*last]);
	*last = *last - 1;
	while(pos < *last) {
		if(2 * pos > *last) {
			break;
		} else if((2 * pos + 1) > *last) {
			if(h[2 * pos]->cost < h[pos]->cost) {
				swap(&h[2 * pos], &h[pos]);
				p[h[pos]->nod] = pos;
				p[h[2 * pos]->nod] = 2 * pos;
				pos = 2 * pos;
			} else {
				break;
			}
		} else if((h[2 * pos]->cost < h[pos]->cost) || (h[2 * pos + 1]->cost < h[pos]->cost)) {
			if(h[2 * pos]->cost < h[2 * pos + 1]->cost) {
				swap(&h[2 * pos], &h[pos]);
				p[h[pos]->nod] = pos;
				p[h[2 * pos]->nod] = 2 * pos;
				pos = 2 * pos;
			} else {
				swap(&h[2 * pos + 1], &h[pos]);
				p[h[pos]->nod] = pos;
				p[h[2 * pos + 1]->nod] = 2 * pos + 1;
				pos = 2 * pos + 1;
			}
		} else {
			break;
		}
	}
}

void insert(arc** h, int val, int c, int* last, int* p) {
	*last = *last + 1;
	arc* a = (arc*)malloc(sizeof(arc));
	a->nod = val;
	a->cost = c;
	h[*last] = a;
	int pos = *last;
	p[h[pos]->nod] = pos;
	while(pos > 1) {
		if(h[pos / 2]->cost > h[pos]->cost) {
			swap(&h[pos / 2], &h[pos]);
			p[h[pos]->nod] = pos;
			p[h[pos / 2]->nod] = pos / 2;
			pos = pos / 2;
		} else {
			break;
		}
	}
}

int main() {
	FILE* fin = fopen("dijkstra.in", "r");
	int n, m;
	fscanf(fin, "%d %d\n", &n, &m);
	int i, j;
	vector* g = (vector*)malloc((n + 1) * sizeof(vector));
	for(i=0; i<=n; i++) {
		g[i] = vec_new(0);
	}
	int a, b, c;
	for(j=0; j<m; j++) {
		fscanf(fin, "%d %d %d\n", &a, &b, &c);
		vec_push_back(g[a], b, c);
	}
	fclose(fin);
	
	int* d = (int*)calloc((n + 1), sizeof(int)); //distances from the source
	int* state = (int*)calloc((n + 1), sizeof(int)); //state of the nodes
	int* p = (int*)calloc((n + 1) , sizeof(int)); //positions in the heap
	arc** heap = (arc**)malloc((n + 1) * sizeof(arc*));
	int last = 0; //size of the heap
	state[1] = 1;
	d[1] = 0;
	insert(heap, 1, 0, &last, p);
	
	int x, y;
	while(last != 0) {
		x = heap[1]->nod;
		if(state[x] == 2) {
			delete(heap, 1, &last, p);
			continue;
		}
		state[x] = 2;
		d[x] = heap[1]->cost;
		for(i=0; i<g[x]->size; i++) {
			y = g[x]->data[i].nod;
			if(state[y] == 0) {
				insert(heap, y, d[x] + g[x]->data[i].cost, &last, p);
				state[y] = 1;
			} else if(state[y] == 1) {
				if(heap[p[y]]->cost > d[x] + g[x]->data[i].cost) {
					delete(heap, p[y], &last, p);
					insert(heap, y, d[x] + g[x]->data[i].cost, &last, p);
				}
			}
		}
		delete(heap, 1, &last, p);
	}
	
	FILE* fout = fopen("dijkstra.out", "w");
	for(i=2; i<=n; i++) {
		fprintf(fout, "%d ", d[i]);
	}
	fprintf(fout, "\n");
	free(p);
	free(d);
	free(state);
	free(heap);
	for(i=0; i<=n; i++) {
		vec_free(g[i]);
	}
	fclose(fout);
	return 0;
}