#include <fstream>
#include <iostream>
#include <list>
#include <climits>
#define MAX_NODES 50001
using namespace std;

ifstream ifs("dijkstra.in");
ofstream ofs("dijkstra.out");


typedef struct Arc 
{
	int dest;
	int weight;
} Arc;

typedef struct HeapNode
{
	int label;
	long long cost;
} HeapNode;

long long D[MAX_NODES]; 
HeapNode HEAP[MAX_NODES];
list<Arc*>* ADJ[MAX_NODES];

int HEAP_SIZE;

void swap(HeapNode A[], int i, int j)
{
	HeapNode aux = A[i];
	A[i] = A[j];
	A[j] = aux;
}

void sift_down(int i) 
{
	int left = i * 2;
	int right =  left + 1;
	int min = -1;
	
	if (left <= HEAP_SIZE) min = left;
	if (right <= HEAP_SIZE && HEAP[right].cost < HEAP[left].cost) min = right;
	
	if (min != -1 && HEAP[min].cost < HEAP[i].cost)
	{	
		swap(HEAP, i, min);
		sift_down(min);
	}
}

void sift_up(int i)
{
	int p = i / 2;
	if (p > 0 && HEAP[p].cost > HEAP[i].cost)
	{
		swap(HEAP, p, i);
		sift_up(p);
	}
}

void heapify(int n)
{
	HEAP_SIZE = n;
	for (int i = HEAP_SIZE / 2; i > 0; --i)
		sift_down(i);
}

HeapNode extract_top() 
{
	if (HEAP_SIZE > 0)
	{
		HeapNode top = HEAP[1];
		
		if (--HEAP_SIZE > 0)
		{
			HEAP[1] = HEAP[HEAP_SIZE+1];
			sift_down(1);
		}
		
		return top;
	}
}


void init(int m)
{
	for (int i = 0; i < m; ++i)
	{
		int a, b, c;
		ifs >> a >> b >> c;
		
		if (ADJ[a] == 00)
		{
			ADJ[a] = new list<Arc*>();
		}
		
		Arc* arc = new Arc;
		arc->dest = b;
		arc->weight = c;
		
		list<Arc*> *neighbors = ADJ[a];
		neighbors->push_back(arc);
	}
}

void relax(int u, int v, int weight)
{
	if (D[v] > D[u] + weight)
		D[v] = D[u] + weight;
}

void init_unique_source(int n, int source)
{
	for (int i = 1; i <= n; ++i)
	{
		HEAP[i].label = i;
		HEAP[i].cost = LLONG_MAX;

		D[i] = LLONG_MAX;
	}
		
	
	HEAP[source].label = source;
	HEAP[source].cost = 0;
	
	D[source] = 0;
}

void print_result(int n)
{
	for (int i = 2; i <= n; ++i)
		ofs << (D[i] == LLONG_MAX ? 0 : D[i]) << " ";
}

void dijkstra(int n, int source)
{
	init_unique_source(n, source);
	heapify(n);
	
	while (HEAP_SIZE > 0)
	{
		HeapNode node = extract_top();
		
		list<Arc*>* neighbors = ADJ[node.label];
		if (neighbors)
			for (list<Arc*>::iterator it = neighbors->begin(); it != neighbors->end(); ++it)
				relax(node.label, (*it)->dest, (*it)->weight);
	}
	
}

int main()
{
	int n, m; ifs >> n >> m;
	
	init(m);
	dijkstra(n, 1);
	print_result(n);
	
	return 0;
}