#include <stdio.h>

#define NMAX 50005
#define INF 1 << 30

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

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

nod *m[NMAX];


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 swap(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;
	if ( k <= 1) return;
	t = k >> 1;
	if ( d[h[t]] > d[h[k]])
	{
		swap(t, k);
		HeapUp(t);
	}
}

void HeapDw(int k)
{
	int st, dr, i, l;
	l = k << 1;
	if ( l <= nh)
	{
		st = h[ l ];
		if ( l | 1 <= nh)
			dr = h[ l | 1];
		else
			dr = st - 1;
		if ( st > dr)
			i = l;
		else
			i = l | 1;
		if ( d[h[i]] < d[h[k]] )
		{
			swap(i, k);
			HeapDw(i);
		}
	}
}


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


int main()
{
	int i, j, 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 = 1; i <= N; i++)
	{
		d[i] = INF;
		h[i] = i;
		poz[i] = i;
	}
	d[1] = 0;

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

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



	return 0;
}