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

#define INFI 0x3f

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

int n, m, d[50005];

struct nod * nds[50005];

int heap[50005], heapSize = 0;

int dheap[50005];

#define DIM 50000  
   
char buf[DIM];  

int poz = 0;

int scan()  
{  
    int x = 0;  
    while(buf[poz] < '0' || buf[poz] > '9')  
        if(++poz == DIM)  
            fread(buf, 1, DIM, stdin), poz = 0;  
    while(buf[poz] >= '0' && buf[poz] <= '9')  
    {  
        x = x*10 + (buf[poz]-'0');  
        if(++poz == DIM)  
            fread(buf, 1, DIM, stdin), poz = 0;  
    }  
        return x;  
}  

void addEdge(int s, int d, int 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()
{
	int i, t1, t2, t3;

	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	fread(buf, 1, DIM, stdin); 

//	scanf("%d%d", &n, &m);
	n = scan();
	m = scan();

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


void make_heap(int x)
{
	int 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(int x)
{
	int 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;
	}
}

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

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

	heapSize--;

	make_heap(1);

	return min;
}

int main()
{
	int 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("%d ", d[i]);
	}

	return 0;
}