#include <stdio.h>

#define INF 1 << 30
#define NMAX 50005

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

nod *m[NMAX];

int N, M, d[NMAX], poz[NMAX], h[NMAX], nh;


void adaug(int a, int b, int c)
{
	nod *aux;
	aux = new nod;
	aux -> v = b;
	aux -> cost = c;
	aux -> next = m[a];
	m[a] = aux;
}

void intoarce(int i, int j)
{
	int aux;
	aux = h[i];
	h[i] = h[j];
	h[j] = aux;
	poz[h[i]] = i;
	poz[h[j]] = j;
}

void HeapUp(int k)
{
	int t;
	t = k << 1;
	while ( d[h[t]] > d[h[k]] && k > 1 )
	{
		intoarce(t, k);
		k = t;
		t = k << 1;
	}
}

void HeapDw(int k)
{
	int st, dr, i;

	if ( 2 * k <= nh)
	{
		st = h[2 * k];

		if ( 2 * k + 1 <= nh)
			dr = h[2 * k + 1];
		else
			dr = st - 1;
		if ( st > dr )
			i = 2 * k;
		else
			i = 2 * k + 1;

		if ( d[h[k]] > d[h[i]])
		{
			intoarce(k, i);
			HeapDw(i);
		}
	}
}



int main()
{
	int i, a, b, c, min;
	nod *p;

	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d %d", &N, &M);

	for ( i = 1; i <= M; i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		adaug(a, b, c);
	}

	for ( i = 2; i <= N; i++)
	{
		d[i] = INF;
		poz[i] = -1;
	}
	h[1] = 1;
	poz[1] = 1;
	nh = 1;

	while ( nh )
	{
		min = h[1];
		intoarce(1, nh);
		poz[h[nh]] = -1;
		nh--;
		HeapDw(1);


		for ( p = m[min]; p; p = p-> next)
			if ( d[ p -> v] > d[ min ] + p -> cost )
			{
				d[ p -> v] = d[min] + p -> cost;
				if ( poz[p->v] == -1)
				{
					++nh;
					h[nh] = p -> v;
					poz[ p-> v] = nh;
					HeapUp(nh);
				}
				else
					HeapUp(poz[p->v]);
			}

	}
	for ( i = 2; i <= N; i++)
	printf("%d ", d[i] == INF? 0 : d[i]);


	return 0;
}