#include <algorithm>
#include <climits>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

// Maximum size of the heap.
const size_t MAXN = 50010;
// Heap data type and comparator.
typedef int heap_t;
inline bool cmp_heap(const heap_t &a, const heap_t &b)
{return a < b;}
// The data is stored starting at index 1.
heap_t data[MAXN];
size_t size_data;
/* Contains the indexes of the data organized as
 * a min or a max heap, the top being at position 1.
 */
size_t heap[MAXN], size_heap;
// pos[i] is the position of data[i] in the heap.
size_t pos_heap[MAXN]; 

// Moves the element at heap[pos] up in the heap.
void heap_up(size_t pos)
{
	while (pos/2 && !cmp_heap(data[heap[pos/2]], data[heap[pos]]))
	{
		swap (heap[pos], heap[pos/2]);
		pos_heap[heap[pos]] = pos;
		pos_heap[heap[pos/2]] = pos/2;
		pos /= 2;
	}
}
// Moves the element at heap[pos] down in the heap.
void heap_down(size_t pos)
{
	size_t next;
	while (pos <= size_heap)
	{
		next = pos;
		if (2*pos <= size_heap && !cmp_heap(data[ heap[next] ], data[ heap[pos*2] ]))
			next = 2*pos;
		if (2*pos+1 <=  size_heap && !cmp_heap(data[ heap[next] ], data[ heap[pos*2+1] ]))
			next = 2*pos+1;

		if (next == pos) break;

		swap (heap[pos], heap[next]);
		pos_heap[heap[next]] = next;
		pos_heap[heap[pos]] = pos;
		
		pos = next;
	}
}
 
// Adds the element data[pos] to the heap.
void push_heap(const size_t pos)
{
	heap[++size_heap] = pos;
    pos_heap[pos] = size_heap;
    heap_up(size_heap);
}
// Returns the element which is at the top of the heap.
void delete_heap(size_t pos)
{
	pos = pos_heap[pos];

	swap(heap[pos], heap[size_heap]);
	pos_heap[heap[pos]] = pos;
	pos_heap[heap[size_heap]] = size_heap;

	size_heap -= 1;

	heap_down(pos);
}
// Removes the element at the top of the heap.
heap_t pop_heap()
{
	heap_t temp = data[heap[1]];
    delete_heap(heap[1]);
	return temp;
}
// Initializes the heap.
void init_heap()
{
	for (size_t i = 1; i <= size_data; ++i)
		heap[i] = pos_heap[i] = i;

	size_heap = size_data;
	for (size_t i = size_data/2; i; --i)
		heap_down(i);
}
// After modifying data[pos] this maintains the heap propery.
void update_heap(size_t pos)
{
	pos = pos_heap[pos];

	heap_up(pos);
}
 
// The vertices labels start from 1 and go to n_vertices.
// The directed graph, first is the label, second is the cost associated with it.
vector <pair<size_t, heap_t>> G[MAXN];
size_t parent[MAXN], n_vertices;
heap_t *dist = data;
const heap_t INF = INT_MAX; 

void dijkstra(size_t start)
{
	fill (dist, dist+n_vertices+2, INF);
	parent[start] = 0;
	dist[start] = 0;
	size_data = n_vertices;
	init_heap();

	for (size_t i = 1; i < n_vertices && size_heap; ++i) // iterate n_vertices-1 times
	{
		heap_t v = heap[1]; // the vertex which has the smallest dist.
		pop_heap();

		if (dist[v] == INF) break;

		for (auto &next : G[v])
			if (dist[next.first] > dist[v] + next.second)
			{
				parent[next.first] = v;
				dist[next.first] = dist[v] + next.second;
				update_heap(next.first);
			}
	}
}

int main()
{
	ifstream fin ("dijkstra.in");
	ofstream fout ("dijkstra.out");

	size_t m;
	fin >> n_vertices >> m;
	for (; m; --m)
	{
		size_t x, y;
		heap_t c;
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y, c));
	}

	dijkstra(1);

	for (size_t v = 2; v <= n_vertices; ++v)
		if (dist[v] == INF)
			fout << "0 ";
		else fout << dist[v] << ' ' ;
	fout << endl;

	fout.close();
	return EXIT_SUCCESS;
}