#include <cstdio>
#include <climits>
const int maxn = 50001;
const int inf = INT_MAX;

FILE *f = fopen("dijkstra.in", "r"), *g = fopen("dijkstra.out", "w");

// data segment
struct graf {
	int nod, cost;
	graf* next;
};

int n, m;
int d[maxn];
int h[maxn];
int poz[maxn], k;
graf *a[maxn];

void swap(int x, int y) {
	h[x] = h[x] ^ h[y];
	h[y] = h[x] ^ h[y];
	h[x] = h[x] ^ h[y];
}


void add(int where, int what, int cost) {
	graf *q = new graf;
	q->nod = what;
	q->cost = cost;
	q->next = a[where];
	a[where] = q;
}


void read() {
	int start, end, cost;
	fscanf(f, "%d %d", &n, &m);
	for (int i = 0; i < m; ++i) {
		fscanf(f, "%d %d %d", &start, &end, &cost);
		add(start, end, cost);
	}
}

void upheap(int what) {
	int tata;
	while (what > 1) {
		tata = what >> 1;

		if (d[h[what]] < d[h[tata]]) {
			poz[h[what]] = tata;
			poz[h[tata]] = what;
			swap(tata, what);

			what = tata;
		}
		else {
			what = 1;
		}
	}
}

void downheap(int what) {
	int f;
	while (what <= k) { // trebuie sa fie mai mic ca lim sup
		f = what;
		if ((what << 1) <= k) {  // exista fiu stg
			f = what << 1;
			if (f + 1 <= k && d[h[f + 1]] < d[h[f]])
				// exista fiu drept si e mai aproape de sursa 
				++f;
		}
		else 
			return;
		if (d[h[what]] > d[h[f]]) {
			poz[h[what]] = f;
			poz[h[f]] = what;

			swap(f, what);

			what = f;
		}
		else return;
	}
}

void dijkstra_heap() {
	// init
	for (int i = 2; i <= n; ++i)
		d[i] = inf, poz[i] = -1;
	// introducing first vertex in min-heap
	poz[1] = 1;
	h[++k] = 1;

	while (k) {  // while there is at least a vertex in heap
		// extract min from heap 
		int min = h[1];
		swap(1, k);
		--k;
		// mark new first elem as the first
		poz[h[1]] = 1;
		downheap(1);  // respect heap law

		graf *q = a[min];  // start to refresh vertices dist.
		while (q) {
			if (d[q->nod] > d[min] + q->cost) {  // refresh dist.
				d[q->nod] = d[min] + q->cost;

				if (poz[q->nod] != -1) {  // refresh poz in heap
					upheap(poz[q->nod]);
				}
				else {  // it isn't in heap
					h[++k] = q->nod;
					poz[q->nod] = k;
					upheap(k);
				}
			}
			q = q->next;  // go through the adjency list of extrated heap item
		}
		
	}
}

int main()
{
	read();
	dijkstra_heap();
	for (int i = 2; i <= n; ++i) {
		fprintf(g, "%d ", d[i] != inf ? d[i] : 0);
	}
	fprintf(g, "\n");
	return 0;
}