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

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;
vector< 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)
{
	register int T;

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

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

void down_heap(int poz)
{
	register int L;
	register int R;
	register int aux_poz;

	while (true)
	{
		if (poz <= nr_heap)
			return;

		 L = 2 * poz;
		 R = 2 * poz + 1;
		
		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;
/*
		loc[heap[poz]] = aux_poz;
		loc[heap[aux_poz]] = poz;
*/
		swap(heap[poz], heap[aux_poz]);
		poz = 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;
	//priority_queue<int> Q;

	//Q.push(start_node);
	insert_heap(start_node);
	
	while (nr_heap)//!Q.empty())
	{
		int nod = heap[1];//Q.top();
		//Q.pop();
		delete_heap();

		for (vector<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;
				
				//Q.push((*it)->right);	
				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] <<" ";
};