#include <stdio.h>
#include <stdlib.h>
 
#define NMAX 50005
#define INF 1 << 30 
 
 int n, m;

//----------------Graph structures----------------------------------------------
typedef struct Node {
	int weight;
	int dest;
	struct Node* next;
} Node;

typedef struct AdjList {
	struct Node *head;		
	
} AdjList;

typedef struct Graph {
	int n;
	struct AdjList *list;
} Graph;

Node* newNode(int dest, int weight) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->dest = dest;
	newNode->weight = weight;
	newNode->next = NULL;

	return newNode;
}

Graph* createGraph(int n) {
	Graph* newGraph = (Graph*)malloc(sizeof(Graph));
	newGraph->n = n;
	newGraph->list = (AdjList*)malloc(n * sizeof(AdjList));

	for (int i = 0; i < n; i++) 
		newGraph->list[i].head = NULL;

	return newGraph;
}

void addEdge(Graph* graph, int source, int dest, int weight) {
	Node* node = newNode(dest, weight);
	node->next = graph->list[source].head;
	graph->list[source].head = node;
}


//------------------------------------------------------------------------------

//---------------Min heap structure --------------------------------------------
typedef struct MinHeapNode {
	int node;
	int distance;

} MinHeapNode; 

typedef struct MinHeap {
	int size;
	int capacity;
	int *pos;
	MinHeapNode** array;
} MinHeap;

MinHeapNode* newMinHeapNode(int node, int distance) {
	MinHeapNode* minHeapNode = (MinHeapNode*)malloc(sizeof(MinHeapNode));
	minHeapNode->node = node;
	minHeapNode->distance = distance;

	return minHeapNode;
}

MinHeap* createMinHeap(int capacity) {
	MinHeap* newMinHeap = (MinHeap*)malloc(sizeof(MinHeap));
	newMinHeap->pos = (int*)malloc(capacity * sizeof(int));
	newMinHeap->size = 0;
	newMinHeap->capacity = capacity;
	newMinHeap->array = (MinHeapNode**)malloc(capacity * sizeof(MinHeapNode));

	return newMinHeap;
}

void swapMinHeapNode(MinHeapNode** a, MinHeapNode** b) {
	MinHeapNode* t = *a;
	*a = *b;
	*b = t;
}

void minHeapify(MinHeap* heap, int idx) {
	int smallest, left, right;
	smallest = idx;
	left = 2 * idx + 1;
	right = 2 * idx + 2;

	if (left < heap->size && 
		heap->array[left]->distance < heap->array[smallest]->distance) {
		smallest = left;
	}

	if (right < heap->size && 
		heap->array[right]->distance < heap->array[smallest]->distance) {
		smallest = right;
	}

	if (smallest != idx) {
		MinHeapNode* smallestNode = heap->array[smallest];
		MinHeapNode* idxNode = heap->array[idx];

		heap->pos[smallestNode->node] = idx;
		heap->pos[idxNode->node] = smallest;

		swapMinHeapNode(&heap->array[smallest], &heap->array[idx]);

		minHeapify(heap, smallest);
	}
}

int isEmpty(MinHeap* heap) {
	return heap->size == 0;
}

MinHeapNode* extractMin(MinHeap* heap) {
	if (isEmpty(heap)) 
		return NULL;

	MinHeapNode* root = heap->array[0];

	MinHeapNode* lastNode = heap->array[heap->size - 1];
	heap->array[0] = lastNode;

	heap->pos[root->node] = heap->size - 1;
	heap->pos[lastNode->node] = 0;

	heap->size--;
	minHeapify(heap, 0);

	return root;
}

void decreaseKey(MinHeap* heap, int node, int dist) {
	int i = heap->pos[node];

	heap->array[i]->distance = dist;

	while(i && heap->array[i]->distance < heap->array[(i - 1) / 2]->distance) {
		heap->pos[heap->array[i]->node] = (i - 1) / 2;
		heap->pos[heap->array[(i - 1) / 2]->node] = i;
		swapMinHeapNode(&heap->array[i], &heap->array[(i - 1) / 2]);

		i = (i - 1) / 2;
	}
}

bool isInMinHeap(MinHeap* heap, int node) {
	if(heap->pos[node] < heap->size)
		return true;
	return false;
}	

//------------------------------------------------------------------------------

//--------------------Utility --------------------------------------------------

void printArr(int dist[], int n) {
	for (int i = 1; i < n; i++)
		printf("%d ", dist[i] == INF ? 0 : dist[i]);
}



//------------------------------------------------------------------------------

//--------------------Dijkstra -------------------------------------------------
void dijkstra(Graph* graph, int src) {
	int n = graph->n;
	int dist[n];

	MinHeap* heap = createMinHeap(n);

	for (int i = 0; i < n; i++) {
		dist[i] = INF;
		heap->array[i] = newMinHeapNode(i, dist[i]);
		heap->pos[i] = i;
	}

	heap->array[src] = newMinHeapNode(src, dist[src]);
	heap->pos[src] = src;
	dist[src] = 0;
	decreaseKey(heap, src, dist[src]);

	heap->size = n;

	while(!isEmpty(heap)) {
		MinHeapNode* minNode = extractMin(heap);
		int chosen_vertex = minNode->node;

		Node* neighbour = graph->list[chosen_vertex].head;
		while(neighbour) {
			int neighbourVertex = neighbour->dest;

			if(isInMinHeap(heap, neighbourVertex) && dist[chosen_vertex] != INF && neighbour->weight + dist[chosen_vertex] < dist[neighbourVertex])	{
				
				dist[neighbourVertex] = dist[chosen_vertex] + neighbour->weight;
				decreaseKey(heap, neighbourVertex, dist[neighbourVertex]);

			}

			neighbour = neighbour->next;
		}
	}

	printArr(dist, n);
}


//------------------------------------------------------------------------------




int main() {
 
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
     
 	scanf("%d %d\n", &n, &m);

 	Graph* graph = createGraph(n);

    int a, b, c;
    for (int i = 0 ; i < m; i++) {
        scanf("%d %d %d\n", &a, &b, &c);
        addEdge(graph, a - 1, b - 1, c); 
    }
 
    dijkstra(graph, 0);
 
    return 0;
}