#include <stdio.h>

#define NMAX 50001
#define INF 1 << 30

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

nod *m[NMAX];


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

void adaug(int x, int y, int c)
{
	nod *aux;
	aux = new nod;
	aux -> v = y - 1;
	aux -> c = c;
	aux -> next = m[x - 1];
	m[x - 1] = 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 HeapDw(int r, int k)
{
	int st, dr, i;
	if ( 2 * r + 1 <= k)
	{
		st = h[ 2 * r + 1];
		if ( 2 * r + 2 <= k )
			dr = h[2 * r +2];
		else
			dr = st - 1;
		if ( st > dr)
			i = 2 * r + 1;
		else
			i = 2 * r + 2;

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


void HeapUp(int k)
{
	int t;
	if ( k <= 0)
		return;
	t = ( k - 1) / 2;
	if ( d[h[k]] < d[h[t]])
	{
		intoarce(k, t);
		HeapUp(t);
	}
}


void BuildH(int k)
{
	int i;
	for ( i = 1; i < k; i++)
		HeapUp(i);
}

int scoate_heap()
{
	intoarce(0, nh - 1);
	poz[h[nh-1]] = 0;
	nh--;
	HeapDw(0, nh-1);
	return h[nh];
}

int main()
{
	int i, x, y, c, no;
	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", &x, &y, &c);
		adaug(x, y, c);
	}

	for ( i = 0; i <= N; i++)
		d[i] = INF;

	for ( p = m[0]; p; p = p -> next)
		d[p -> v] = p -> c;

	d[0] = 0;

	for ( i = 0; i < N; i++)
	{
		h[i] = i + 1;
		poz[i+1] = i;
	}

	BuildH(N);
	nh = N;
	while ( nh > 0)
	{
		no = scoate_heap();
		for ( p = m[no]; p; p = p -> next)
			if ( d[ p -> v]  > d[no] + p -> c)
			{
				d[ p -> v] = d[no] + p -> c;
				//t[ p-> v] = no;
				HeapUp(poz[p -> v]);

			}
	}

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

	return 0;
}