#include <cstdio>
#include <cstdlib>
#include <cstring>

#define INFI 0x3f

struct nod 
{
	long long d, c;
	struct nod * next;
};

long long n, m, d[50005];

struct nod * nds[50005];

long long heap[50005], heapSize = 0;

long long dheap[50005];

void addEdge(long long s, long long d, long long c)
{
	struct nod * cnod;
	
	cnod = (nod *) malloc(sizeof(struct nod));

	cnod->d = d;
	cnod->c = c;
	
	cnod->next = nds[s];
	
	nds[s] = cnod;
}

void read()
{
	long long i, t1, t2, t3;

	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	scanf("%lld%lld", &n, &m);

	for(i = 0; i < m; i++)
	{
		scanf("%lld%lld%lld", &t1, &t2, &t3);	
		addEdge(t1, t2, t3);	
//		addEdge(t2, t1, t3);
	}
}


void make_heap(long long x)
{
	long long minX, t1;

	if(2*x <= heapSize && d[heap[2*x]] < d[heap[x]])
	{
		minX = 2*x;
	}
	else
	{
		minX = x;
	}
	
	if(2 * x + 1 <= heapSize && d[heap[2*x+1]] < d[heap[minX]])
	{
		minX = 2*x+1;	
	}
	
	if(minX != x)
	{	
		t1 = heap[x];
		heap[x] = heap[minX];
		heap[minX] = t1;

		t1 = dheap[heap[x]];
		dheap[heap[x]] = dheap[heap[minX]];
		dheap[heap[minX]] = t1;

		make_heap(minX);
	}

}


void decr_heap(long long x)
{
	long long i, t1;
	
	i = dheap[x];

	while(i > 1 && d[heap[i/2]] > d[x])
	{
		t1 = heap[i];
		heap[i] = heap[i/2];
		heap[i/2] = t1;

		t1 = dheap[heap[i/2]];
		dheap[heap[i/2]] = dheap[heap[i]];
		dheap[heap[i]] = t1;

		i = i/2;
	}
}

long long extract_min()
{
	long long min = heap[1];

	heap[1] = heap[heapSize];
	dheap[min] = 0;
	dheap[heap[heapSize]] = 1;

	heapSize--;

	make_heap(1);

	return min;
}

int main()
{
	long long i, cs;
	struct nod * cnod;

	read();

//	memset(d, INFI, sizeof(d));

	for(i = 1; i <= n; i++)
		d[i] = 1 << 30;
	
	d[1] = 0;
	
	for(i = 1; i <= n; i++)
	{	
		heap[i] = i;
		dheap[i] = i;
	}	
	
	heapSize = n;

	for(i = heapSize/2; i >= 1; i--)
	{
		make_heap(i);
	}

	while(heapSize > 0)
	{
		cs = extract_min();
	
		cnod = nds[cs];

		while(cnod)
		{
			if(d[cnod->d] > d[cs] + cnod->c)
			{
				d[cnod->d] = d[cs] + cnod->c;
			
				decr_heap(cnod->d);
			}

			cnod = cnod->next;
		}
	}

	for(i = 2; i <= n; i++)
	{
		d[i] == 1 << 30 ? printf("0 ") : printf("%lld ", d[i]);
	}

	return 0;
}