#include <iostream>
#include <fstream>
#include <vector>
#include <time.h>
#include <algorithm>
#include <assert.h>

using namespace std;

const int _MAX_NODES = 50001;
const int _MAX_EDGES = 250001;
const int oo = 0x3f3f3f3f;

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

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

	return 0;
};

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

int n, m;
vector< struct node *> List[_MAX_NODES];

int dist[_MAX_NODES];
int tata[_MAX_NODES];
int used[_MAX_NODES];

/*	start heap	*/

int nr_heap;
node * heap[_MAX_EDGES];

void up_heap(int poz)
{
	int T;
	while (true)
	{
		if (poz <= 1)
			return;

		T = poz >> 1;

		if (heap[T]->cost > heap[poz]->cost)
		{
			swap(heap[poz], heap[T]);
			poz = T;
		}
		else
			break;
	}
}

void down_heap(int poz)
{
	int L = 2 * poz;
	int R = 2 * poz + 1;

	int aux_pos = poz;

	if (L <= nr_heap)
		if (heap[L]->cost < heap[aux_pos]->cost)
			aux_pos = L;

	if (R <= nr_heap)
		if (heap[R]->cost < heap[aux_pos]->cost)
			aux_pos = R;

	if (aux_pos != poz)
	{
		swap(heap[poz], heap[aux_pos]);
		down_heap(aux_pos);
	}
}

void insert_heap(struct node *aux)
{
	heap[++nr_heap] = aux;
	up_heap(nr_heap);
}

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

void read()
{
	ifstream f("dijkstra.in", fstream::in);

	f >> n >> m;

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

void solve()
{
	for (int i = 1; i <=n; ++i)
	{
		dist[i] = oo;
		tata[i] = -1;
		used[i] = 0;
	}

	//nodul de la care plec
	dist[1] = 0;
	tata[1] = 0;
	used[1] = 1;
	for (vector<struct node *>::iterator it = List[1].begin(); it != List[1].end(); ++it)
	{
		dist[(*it)->right] = (*it)->cost;
		tata[1] = 1;

		insert_heap( *it );
	}

	while (nr_heap != 0)
	{
		node * aux = heap[1];
		delete_heap();

		for (vector<struct node *>::iterator it = List[aux->right].begin(); it != List[aux->right].end(); ++it)
		{
			if (dist[(*it)->right] > dist[aux->right] + (*it)->cost)
			{
				dist[(*it)->right] = dist[aux->right] + (*it)->cost;

				insert_heap(*it);
			}
		}
	}
};

void check()
{
};

void print()
{
	ofstream ofs("dijkstra.out", fstream::out);
	for (int i = 2; i <= n; ++i)
		ofs<<dist[i]<<" ";
	//system("PAUSE");
};