#include <fstream>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;

ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

struct edge {
	int y, cost;
};

struct heap {
	int val, vertex;
};

#define INF 999293192


const int maxn = 50000;
int solution[maxn+1], N, M, real_N;
heap HEAP[maxn + 1];
vector<edge> edges[maxn + 1];
int v_location[maxn + 1];

inline int father(int node) {
	return node / 2;
}

inline int right_son(int node) {
	return 2 * node + 1;
}

inline int left_son(int node) {
	return 2 * node;
}

inline int get_min() {
	return HEAP[1].val;
}

void heap_up(int pos);
void heap_down(int pos);
void cut(int pos);
void alter(int pos, int val);
void heap_dijkstra();
void read();


int main()
{
	read();
	heap_dijkstra();
	return 0;
}

void read()
{
	fi >> N >> M;
	for (int i = 1;i <= M;i++)
	{
		int x, y, cost;
		fi >> x >> y >> cost;
		edges[x].push_back({ y,cost });
	}
	real_N = N;
	HEAP[1].val = 0;
	HEAP[1].vertex = 1;
	v_location[1] = 1;							//location of vertex i in the heap					
	for (int i = 2;i <= N;i++)
		HEAP[i] = { INF,i }, v_location[i] = i;
	return;
}


void heap_down(int pos)
{
	int son;
	do {
		son = 0;
		if (left_son(pos) <= N)
		{
			son = left_son(pos);
			if (right_son(pos) <= N && HEAP[right_son(pos)].val < HEAP[left_son(pos)].val)
				son = right_son(pos);
			if (HEAP[son].val >= HEAP[pos].val)
				son = 0;
		}
		if (son)
		{
			swap(v_location[HEAP[pos].vertex], v_location[HEAP[son].vertex]);
			swap(HEAP[son], HEAP[pos]);
			pos = son;
		}

	} while (son);

	return;
}

void heap_up(int pos)
{
	int val = HEAP[pos].val;
	int node = HEAP[pos].vertex;
	int initial_pos = pos;
	while (pos >= 1 && HEAP[pos].val <= HEAP[father(pos)].val)
	{
		v_location[HEAP[father(pos)].vertex] = v_location[HEAP[pos].vertex];
		HEAP[pos] = HEAP[father(pos)];
		pos = father(pos);
	}
	HEAP[pos].val = val;
	HEAP[pos].vertex = node;
	v_location[HEAP[pos].vertex] = pos;
	return;
}

void cut(int pos)
{
	v_location[HEAP[N].vertex] = v_location[HEAP[pos].vertex];
	v_location[HEAP[pos].vertex] = INF;
	HEAP[pos] = HEAP[N];
	N--;
	if (pos > 1 && HEAP[pos].val < HEAP[father(pos)].val)
		heap_up(pos);
	else heap_down(pos);
}

void alter(int pos, int  val)
{
	HEAP[pos].val = val;
	if (pos > 1 && HEAP[pos].val < HEAP[father(pos)].val)
		heap_up(pos);
	else heap_down(pos);
}

void heap_dijkstra()
{
	while (N)
	{
		int node = HEAP[1].vertex;
		int initial = HEAP[1].val;
		solution[HEAP[1].vertex] = HEAP[1].val;
		cut(1);
		for (int i = 0;i < edges[node].size();i++)
		{
			int vertex = edges[node][i].y;
			int val = edges[node][i].cost;
			if (v_location[vertex] != INF && val + initial < HEAP[v_location[vertex]].val)
				alter(v_location[vertex], val + initial);
		}
	}
	for (int i = 2;i <= real_N;i++)
		fo << solution[i] << " ";
}