#include <stdio.h>
#include <stdlib.h>

#define MAXN 50001

struct graph
{
	int edge, cost;
	struct graph *next;
} *G[MAXN];

const int INF = 1 << 30;
unsigned short heap[MAXN], posInHeap[MAXN], N, heapL;
int dist[MAXN];

void read();
void heapUp(unsigned short pos);
int popHeap();

int main()
{
	unsigned short i, min = 0;
	FILE *out = fopen("dijkstra.out", "w");
	struct graph *p;
	
	read();
	 
	heapL = N;
	for(i = 1; i <= N; i++)	
		dist[i] = INF, heap[i] = posInHeap[i] = i;
	dist[1] = 0;
	
	for(i = 0; i < N && min != INF; i++)
	{
		min = popHeap();
		if(min != INF)
		{		
			for(p = G[min]; p; p = p->next)
				if(dist[min] + p->cost < dist[p->edge])
				{
					dist[p->edge] = dist[min] + p->cost;
					heapUp(p->edge);
				}
		}
	}
	
	for(i = 2; i <= N; i++)
		if(dist[i] == INF)
			fprintf(out, "0 ");
		else
			fprintf(out, "%d ", dist[i]);
	fprintf(out, "\n");
	
	fclose(out);	
	return 0;
}

int popHeap()
{
	unsigned short temp, pos, min, sw;

	posInHeap[ heap[1] ] = 0;
	posInHeap[ heap[heapL] ] = 1;
	
	temp = heap[1];
	heap[1] = heap[heapL];
	heap[heapL] = temp;
	heapL--;
	
	pos = min = 1;
	
	for(sw = 1; sw;)
	{
		sw = 0;
		if(2*pos < heapL && dist[ heap[min] ] > dist[ heap[2*pos] ]) 
			min = 2*pos, 
			sw = 1;
		if(2*pos+1 < heapL && dist[ heap[min] ] > dist[ heap[2*pos+1] ]) 
			min = 2*pos+1, 
			sw = 1;
		
		temp = heap[pos];
		heap[pos] = heap[min];
		heap[min] = temp;
		
		posInHeap[ heap[min] ] = min;
		posInHeap[ heap[pos] ] = pos;
		
		pos = min;
	}
	
	return heap[ heapL+1 ];
}

void heapUp(unsigned short pos)
{
	unsigned short temp;
	
	for(pos = posInHeap[pos]; pos != 1 && dist[ heap[pos] ] < dist[ heap[pos/2] ]; pos /= 2)
	{
		temp = heap[pos];
		heap[pos] = heap[pos/2];
		heap[pos/2] = temp;
		
		posInHeap[ heap[pos] ] = pos;
		posInHeap[ heap[pos/2] ] = pos/2;
	}
}

void read()
{	
	FILE *in = fopen("dijkstra.in", "r");
	int m, a, b, c;
	struct graph *p;
	
	for(fscanf(in, "%hu %d", &N, &m); m; m--)
	{
		fscanf(in, "%d %d %d", &a, &b, &c);
		p = malloc(sizeof(struct graph));
		p->edge = b;
		p->cost = c;
		p->next = G[a];
		G[a] = p;
	}
	
	fclose(in);
}