#include <cstdio>
const int maxn = 50001;
const int inf = 1 << 30;

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

struct graf
{
	int nod, cost;
	graf *next;
};

int n, m;
graf *a[maxn];
int d[maxn];  // distanta de la origine
int h[maxn];  // heap
int poz[maxn];  // ? 
int k;

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

void read()
{
	fscanf(in, "%d %d", &n, &m);

	int x, y, z;
	for (int i = 1; i <= m; ++i)
	{
		fscanf(in, "%d %d %d", &x, &y, &z);
		add(x, y, z);
	}
}

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

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

		if (d[h[tata]] > d[h[what]])
		{
			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)
	{
		f = what;
		if ((what << 1) <= k)
		{
			f = what << 1;
			if (f + 1 <= k)
				if (d[h[f + 1]] < d[h[f]])
					++f;
		}
		else
			return;

		if (d[h[what]] > d[h[f]])
		{
			poz[h[what]] = f;
			poz[h[f]] = what;

			swap(what, f);

			what = f;
		}
		else
			return;
	}
}

void dijkstra_heap()
{
	for (int i = 2; i <= n; ++i)
		d[i] = inf, poz[i] = -1;
	poz[1] = 1;

	h[++k] = 1;

	while (k)  // heap still has unvisited vertex
	{
		int min = h[1];  // mark current min
		swap(1, k);  // put min at the end
		poz[h[1]] = 1;  // mark the moved's item pos as the first in heap
		--k;  // mark the throw of min off the heap

		downheap(1);  // the first item is not obeing the heap law:) and it's punished

		graf *q = a[min];  // get a pointer to the current min vertex

		while (q)
		{
			if (d[q->nod] > d[min] + q->cost)
			{
				d[q->nod] = d[min] + q->cost;  // refresh current vertex dist

				if (poz[q->nod] != -1)  // if it is in heap
					upheap(poz[q->nod]);
				else
				{
					h[++k] = q->nod;  // add it to the heap
					poz[h[k]] = k;  // classic heap insert at the bottom
					upheap(k);
				}
			}
			q = q->next; // parcurg lista de adiacenta
		}
	}
}

int main()
{
	read();
	dijkstra_heap();

	for (int i = 2; i <= n; ++i)
		fprintf(out, "%d ", d[i] == inf ? 0 : d[i]);
	fprintf(out, "\n");

	return 0;
}