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

///////////////////LISTA/////////////////////////

typedef struct tagNode
{
	int vecin;
	int cost;
	struct tagNode *next;
}Node;

typedef struct tagList
{
	Node* start;
}List;

void initList(List *list)
{
	list->start = NULL;	
}

void addList(List *list, int vecin, int cost)
{
    Node *new = malloc(sizeof(Node));
    new->next = list->start;
    new->vecin = vecin;
    new->cost = cost;
    list->start = new;
}

void printList(List *list)
{
	Node *q = list->start;
	printf("LIST :");
	while( q != NULL ){
		printf(" (%d,%d)",q->vecin, q->cost);
		q = q->next;
	}
	printf("\n");
}

/////////////////////////////////////////////////

#define MAXN 50002

enum Type { WHITE=0, GREY, BLACK };

int N,M;
enum Type node_status[MAXN];
int distance[MAXN];

List vecini[MAXN];

//////////////////// HEAP /////////////////////////

typedef struct tagHeapNode{
	int node;
	int distance;
}HeapNode;


struct Heap{
	HeapNode nodes[MAXN];
	int heap_position[MAXN];
	int count;	
};

struct Heap heap;

void swapInt(int* a, int* b)
{
	int aux;
	aux = *a;
	*a = *b;
	*b = aux;
}

void swapHeapNode(HeapNode *a, HeapNode *b)
{
	HeapNode aux;
	aux = *a;
	*a = *b;
	*b = aux;
	
	swapInt( &heap.heap_position[a->node], &heap.heap_position[b->node] );
}

struct Heap heap;

void HeapUp(int node)
{
	while( node != 1 && heap.nodes[node/2].distance > heap.nodes[node].distance ){
		swapHeapNode(&heap.nodes[node/2], &heap.nodes[node]);
		node = node/2;
	}
}

// se presupune ca nu exista in heap
void HeapAdd(int node, int distance)
{
	HeapNode new;
	new.node = node;
	new.distance = distance;
	
	heap.count++;
	heap.nodes[heap.count] = new;
	heap.heap_position[node] = heap.count;
	
//	printf("HeapAdd %d d=%d, count = %d\n",node,distance,heap.count);
	HeapUp(heap.count);	
}

HeapNode HeapPop()
{
	HeapNode ret = heap.nodes[1];
	heap.heap_position[ret.node] = 0;
	heap.nodes[1] = heap.nodes[heap.count];
	heap.heap_position[heap.nodes[1].node] = 1;
	heap.count--;
	
	int node = 1;
	while(1){
		int st,dr,min;
		st = node*2;
		dr = node*2 + 1;
		min = node;
		
		if( st <= heap.count && heap.nodes[min].distance > heap.nodes[st].distance )
			min = st;
		if( dr <= heap.count && heap.nodes[min].distance > heap.nodes[dr].distance )
			min = dr;
			
		if( min == node )
			break;
		else{
			swapHeapNode(&heap.nodes[min], &heap.nodes[node]);
			node = min;			
		}
	}
	
	return ret;
}

void printHeap()
{
	int j;
	for(j=1;j<=heap.count;j++)
		printf("(%4d,%4d,%3d) ",heap.nodes[j].node, heap.nodes[j].distance, heap.heap_position[heap.nodes[j].node]);
	printf("\n\n");
	
}


///////////////////////////////////////////////////

int main(int argc, char* argv[])
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	scanf("%d %d",&N,&M);
	int i,a,b,c;
	for(i=1;i<=N;i++)
		initList(&vecini[i]);
	for(i=0;i<M;i++){
		scanf("%d %d %d",&a,&b,&c);
		addList(&vecini[a],b,c);
	}

	node_status[1] = BLACK;
	HeapAdd(1,0);
	
	while( heap.count != 0 ){
		HeapNode current = HeapPop();
		distance[current.node] = current.distance;
		node_status[current.node] = BLACK;
		
//		printf("Am scos de pe heap nodul %d cu d=%d\n",current.node,current.distance);
//		printHeap();
		
		Node* q = vecini[current.node].start;
		while( q != NULL ){
			if(  node_status[q->vecin] == GREY ){
				int pos = heap.heap_position[q->vecin];
				if( heap.nodes[pos].distance > ( current.distance + q->cost ) ){
//					printf("Update la heap la nodul %d cu distanta de la %d la %d\n",q->vecin,heap.nodes[pos].distance, current.distance + q->cost);
					heap.nodes[pos].distance = current.distance + q->cost;
					HeapUp(pos);
//					printHeap();
				}
			}
			else if( node_status[q->vecin] == WHITE ){
				node_status[q->vecin] = GREY;
				HeapAdd(q->vecin, current.distance + q->cost);
//				printHeap();		
			}
			// BLACK jet
			q = q->next;
		}		
	}
	
	for(i=2;i<=N;i++){
		printf("%d ",distance[i]);
	}
	
	return 0;
}