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

typedef int heap_t;
struct Heap
{
	vector<int> heap, pos_heap;
	vector<heap_t> data;

	void init() {
		heap.resize(data.size());
		pos_heap.resize(data.size());

		iota(heap.begin(), heap.end(), 0);
		iota(pos_heap.begin(), pos_heap.end(), 0);

		for (int hpos = parent(heap.size()); hpos >= 0; --hpos)
			down(hpos);
	}

	void swap_h(int hp1, int hp2) {
		swap(heap[hp1], heap[hp2]);
		pos_heap[heap[hp1]] = hp1;
		pos_heap[heap[hp2]] = hp2;
	}

	bool cmp (int hp1, int hp2)
	{ return data[heap[hp1]] <= data[heap[hp2]]; }
	
	int parent (int hpos)
	{ return hpos > 0 ? (hpos-1)/2 : 0; }

	int first_son (int hpos)
	{ return 2 * hpos + 1; }

	int second_son (int hpos)
	{ return 2* hpos + 2; }

	void up (int hpos) {
		for (; hpos != parent(hpos) && !cmp(parent(hpos), hpos); hpos = parent(hpos))
			swap_h(parent(hpos), hpos);
	}

	void down (int hpos) {
		for (int next = hpos; hpos < heap.size(); hpos = next)
		{
        	if (first_son(hpos) < heap.size() && !cmp(next, first_son(hpos)))
        		next = first_son(hpos);
        	if (second_son(hpos) < heap.size() && !cmp(next, second_son(hpos)))
        		next = second_son(hpos);

        	if (hpos == next) break;
        	swap_h(hpos, next);
		}
	}

	void update(int pos) {
		up(pos_heap[pos]);
		down(pos_heap[pos]);
	}

	void remove (int pos) {
		pos = pos_heap[pos];
		swap_h(pos, heap.size()-1);
		heap.pop_back();
		down(pos);
	}

	heap_t top() {
		return data[heap[0]];
	}

	heap_t pop () {
		heap_t t = data[heap[0]];
		remove(heap[0]);
		return t;
	}
	
	void push (heap_t x) {
		data.push_back(x);
		heap.push_back(data.size() - 1);
		pos_heap.push_back(heap.size() - 1);
		up(heap.size()-1);
	}
};

const int INF = INT_MAX; 
Heap heap;
//END CUT
vector<int> parent;
vector<vector<pair<int, int>>> graph;

void dijkstra(size_t start)
{
	heap.data.resize(graph.size(), INF);
	parent.resize(graph.size(), 0);
	
	heap.data[start] = 0;

	heap.init();

	// Iterate #vertices-1 times.
	for (size_t i = 1; i < graph.size() && heap.heap.size(); ++i)
	{
		// Get the vertex which has the smallest distance
		int v = heap.heap[0];
		heap.pop();

		if (heap.data[v] == INF) break;

		for (auto &next : graph[v])
			if (heap.data[next.first] > heap.data[v] + next.second)
			{
				parent[next.first] = v;
				heap.data[next.first] = heap.data[v] + next.second;
				heap.update(next.first);
			}
	}
}
//BEGIN CUT
int main()
{
	ifstream fin ("dijkstra.in");
	ofstream fout ("dijkstra.out");

	size_t m, n;
	fin >> n >> m;
	graph.resize(n);

	for (; m; --m)
	{
		int x, y,  c;
		fin >> x >> y >> c;
		graph[x-1].push_back(make_pair(y-1, c));
	}

	dijkstra(0);

	for (int v = 1; v < graph.size(); ++v)
		if (heap.data[v] == INF)
			fout << "0 ";
		else fout << heap.data[v] << ' ' ;
	fout << endl;

	fout.close();
	return EXIT_SUCCESS;
}