#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <vector>
#include <list>

using namespace std;

void read();
void solve();
void check();
void print();

const int MAX_NODES = 50001;
const int MAX_EDGES = 250001;

const int oo = 0x3f3f3f3f;

void read();
void solve();
void check();
void print();

struct node
{
	int right, cost;
	node(int right, int cost) { this->right = right; this->cost = cost; };
};

int main()
{
	read();
	solve();
	check();
	print();

	return 0;
}

int n, m;
list< struct node * > List[MAX_NODES];
int dist[MAX_NODES];
int loc[MAX_NODES];
int used[MAX_NODES];

/*	begin heap	*/
int heap[MAX_NODES];
int nr_heap;

void up_heap(int poz)
{
	int T;

	while (true)
	{
		if (poz <= 1) return;
		T = poz >> 1;

		if (dist[heap[T]] > dist[heap[poz]])
		{
			//swap(loc[heap[T]], loc[heap[poz]]);
			loc[heap[T]] = poz;
			loc[heap[poz]] = T;
			swap(heap[T], heap[poz]);
			poz = T;
		}
		else
			return;
	}
}

void down_heap(int poz)
{
	if (poz <= nr_heap)
		return;

	int L = 2 * poz;
	int R = 2 * poz + 1;
	int aux_poz = poz;

	if (L <= nr_heap)
		if (dist[heap[L]] < dist[heap[aux_poz]])
			aux_poz = L;

	if (R <= nr_heap)
		if (dist[heap[R]] < dist[heap[aux_poz]])
			aux_poz = R;

	if (aux_poz == poz)
		return;

	//swap(loc[heap[poz]], loc[heap[aux_poz]]);
	loc[heap[poz]] = aux_poz;
	loc[heap[aux_poz]] = poz;

	swap(heap[poz], heap[aux_poz]);
	down_heap(aux_poz);
}

void insert_heap(int info)
{
	heap[++nr_heap] = info;
	loc[info] = nr_heap;
	up_heap(nr_heap);
}

void delete_heap()
{
	loc[heap[nr_heap]] = 1;
	loc[heap[1]] = -1;
	heap[1] = heap[nr_heap];
	--nr_heap;
	down_heap(1);
}
/*	end heap	*/

void read()
{
	int left, right, cost;

	fstream f("dijkstra.in", ofstream::in);
	f >> n >> m;

	for (int i = 1; i <= m ; ++i)
	{
		f >> left >> right >> cost;
		List[left].push_back(new node(right, cost));
	}
};

void solve()
{
	int start_node = 1;
	
	for (int i = 1; i <= n; ++i)
		dist[i] = oo;

	dist[start_node] = 0;
	insert_heap(start_node);
	
	while (nr_heap)
	{
		int nod = heap[1];
		delete_heap();

		for (list<struct node *>::iterator it = List[nod].begin() ; it != List[nod].end(); it++)
			if (dist[(*it)->right] > dist[nod] + (*it)->cost )
			{
				dist[(*it)->right] = dist[nod] + (*it)->cost;
				
				if (loc[(*it)->right] > 0)
					up_heap(loc[(*it)->right]);
				else
					insert_heap((*it)->right);		
			}
	}
};

void check()
{
};

void print()
{
	ofstream ofs("dijkstra.out", ofstream::out);
	for (int i = 2; i <= n; ++i)
		if (dist[i] == oo)
			ofs << "0 ";
		else
			ofs << dist[i] <<" ";
};