#include <fstream>
#include <iostream>
#include <forward_list>
#include <bitset>
#include <climits>
#define MAX_NODES 50001
#define INF 9999999
using namespace std;

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


typedef struct Arc 
{
	unsigned short dest;
	unsigned short weight;
} Arc;


bitset<MAX_NODES> S;
unsigned short HEAP[MAX_NODES];
unsigned short NODES[MAX_NODES];
unsigned int D[MAX_NODES]; 
forward_list<Arc>* ADJ[MAX_NODES];

int HEAP_SIZE;

void swap(int i, int j)
{
	int aux = HEAP[i];
	HEAP[i] = HEAP[j];
	HEAP[j] = aux;
	
	NODES[HEAP[i]] = i;
	NODES[HEAP[j]] = j;
}

void sift_down(int i) 
{
	int left = i * 2;
	int right =  left + 1;
	int min = -1;

	while (left <= HEAP_SIZE)
	{
		if (left <= HEAP_SIZE) min = left;
		if (right <= HEAP_SIZE && D[HEAP[right]] < D[HEAP[left]]) min = right;
		
		if (min != -1 && D[HEAP[min]] < D[HEAP[i]])
			swap(i, min);
		else
			return;
		
		i = min;
		left = i * 2;
		right = left + 1;
	}
}

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

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

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


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

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

void init_unique_source(int n, int source)
{
	for (int i = 1; i <= n; ++i)
	{
		HEAP[i] = i;
		NODES[i] = i;
		D[i] = INF;
	}
		
	D[source] = 0;
}

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

void dijkstra(int n, int source)
{
	init_unique_source(n, source);
	heapify(n);
	
	while (HEAP_SIZE > 0)
	{
		int u = extract_top();
		S[u] = true;
		
		forward_list<Arc>* neighbors = ADJ[u];
		if (neighbors)
		{
			for (forward_list<Arc>::iterator it = neighbors->begin(); it != neighbors->end(); ++it)
			{	
				int v = it->dest;
				int w = it->weight;
				
				if (!S[v]) 
				{
					relax(u, v, w);
				}
			}
		}
	}
}

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