#include<stdio.h>
#include<limits.h>
#include<malloc.h>

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

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

int n, m;
struct graf *gf[10000];
int d[10000], h[10000],poz[10000],k;

void add(int loc, int val, int cost)
{
	graf *aux = (struct graf*)malloc(sizeof(struct graf));
	aux->nod = val;
	aux->cost = cost;
	aux->next = gf[loc];
	gf[loc] = aux;
}

void citire()
{
	fscanf(in, "%d%d", &n, &m);
	int x, y, z;
	int i;
	for (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 val)
{
	int tata;
	while (val > 1)
	{
		tata = val >> 1;
		if (d[h[tata]] > d[h[val]])
		{
			poz[h[val]] = tata;
			poz[h[tata]] = val;
			swap(tata, val);
			val = tata;
		}
		else
			val = 1;
	}
}

void downheap(int val)
{
	int fiu;
	while (val <= k)
	{
		fiu = val;
		if ((val << 1) <= k)
		{
			fiu = val << 1;
			if (fiu + 1 <= k)
				if (d[h[fiu + 1]] < d[h[fiu]])
					++fiu;
		}
		else
			return;
		if (d[h[val]]>d[h[fiu]])
		{
			poz[h[val]] = fiu;
			poz[h[fiu]] = val;
			swap(val, fiu);
			val = fiu;
		}
		else
			return;
	}
}

void dijkstra_heap()
{
	int i, min;
	for (i = 2; i <= n; ++i)
		d[i] = INT_MAX, poz[i] = -1;
	poz[1] = 1;
	h[++k] = 1;
	while (k)
	{
		min = h[1];
		swap(1, k);
		poz[h[1]] = 1;
		--k;
		downheap(1);
		graf *q = gf[min];
		while (q)
		{
			if (d[q->nod] > d[min] + q->cost)
			{
				d[q->nod] = d[min] + q->cost;
				if (poz[q->nod] != -1)
					upheap(poz[q->nod]);
				else
				{
					h[++k] = q->nod;
					poz[h[k]] = k;
					upheap(k);
				}
			}
			q = q->next;
		}
	}
}

int main()
{
	citire();
	int i;
	struct graf *aux;
	dijkstra_heap();
	for (int i = 2; i <= n; ++i)
		fprintf(out,"%d ", d[i] == INT_MAX ? 0 : d[i]);
	fprintf(out,"\n");
	return 0;
}