#include <stdio.h>
#define maxint 2000000
#define max 50000

FILE *in,*out;
int n,m,r[max],cp,cu=-1,c[max];
typedef struct nod {int inf; int cost; nod *urm;};
nod *v[max];

void add (int x, int y, int z)
{
	nod *p;

	p = new nod;

	p -> inf  = y;
	p -> cost = z;
	p -> urm  = v[x];

	v[x] = p;
}

void addelc(int x)
{
	int i,aux;

	if (cu == max) cu = 0;
		else cu++;

	c[cu] = x;

	i = cu-1;

	while (r[x] < r[c[i]])
	{
		aux = c[i];
		c[i] = c[x];
		c[x] = aux;

		i--;
	}
}

int getelc()
{
	int x;

	x = c[cp];

	if (cp == max) cp = 0;
		else cp++;

	return x;
}

void rezolva ()
{
	int i,x;
	nod *p;

	//se seteaza costul maxim la noduri
	for (i=2; i<=n; i++)
	{
		r[i] = maxint;
	}

	//se adauga primul nod in coada
	addelc(1);

	//se parcurge coada
	while (cp <= cu)
	{
		x = getelc();

		for (p = v[x]; p!=NULL; p=p->urm)
		{
			if (r[x] + p->cost < r[p->inf])
			{
				r[p->inf] = r[x] + p->cost;
				addelc(p->inf);
			}
		}
	}
}

void citeste ()
{
	int i,x,y,z;

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

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

void scrie ()
{
	int i;

	for (i=2; i<=n; i++)
	{
		fprintf(out, "%d ", r[i]);
	}
}

int main ()
{
	in  = fopen("dijkstra.in", "r");
	out = fopen("dijkstra.out", "w");

	citeste();
	rezolva();
	scrie();

	fclose(in);
	fclose(out);
	return 0;
}