#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

const int COST_MAX = 999999;

struct Pair
{
	int nod, cost;
	Pair(int nod = 0, int cost = 0) : nod(nod), cost(cost) {}
};

struct NodGraf
{
	std::vector<Pair> muchii;
	int index;
	int dist;
};

NodGraf graf[50000];
Pair heap[50000];
int heap_pos[50000];
int heap_len = 0;

void heap_swap(int index_a, int index_b)
{
	std::swap(heap_pos[heap[index_a].nod], heap_pos[heap[index_b].nod]);
	std::swap(heap[index_a], heap[index_b]);
}

bool heap_swap_if_greater(int index_a, int index_b)
{
	if(heap[index_a].cost > heap[index_b].cost)
	{
		std::swap(heap_pos[heap[index_a].nod], heap_pos[heap[index_b].nod]);
		std::swap(heap[index_a], heap[index_b]);
		return true;
	}

	return false;
}

void heap_replace(int nod, int cost)
{
	int index = heap_pos[nod];

	heap[index].cost = cost;
	while(index > 0 && heap[index].cost < heap[(index - 1) / 2].cost)
	{
		heap_swap(index, (index - 1) / 2);
		index = (index - 1) / 2;
	}
}

void heap_push(const Pair& nod)
{
	heap_pos[nod.nod] = heap_len;
	heap[heap_len] = nod;
	heap_len++;
}

void heap_pop()
{
	heap_swap(0, heap_len - 1);
	heap_len--;

	int i = 0, st = 0, dr = 0;
	do
	{
		dr = (i + 1) * 2;
		st = dr - 1;

		if(st < heap_len)
		{
			if(dr < heap_len)
			{
				if(heap[dr].cost < heap[st].cost)
				{
					if(!heap_swap_if_greater(i, dr))
						break;

					i = dr;
				}
				else
				{
					if(!heap_swap_if_greater(i, st))
						break;

					i = st;
				}
			}
			else
			{
				if(!heap_swap_if_greater(i, st))
					break;

				i = st;
			}
		}
	} while(st < heap_len);
}

Pair heap_top() { return heap[0]; }

void dijkstra(int n, int start)
{
	for(int i = 0; i < n; i++)
	{
		graf[i].index = i;
		graf[i].dist = (i == start ? 0 : COST_MAX);
		
		heap_push(Pair(i, graf[i].dist));
	}

	while(heap_len > 0)
	{
		Pair vert = heap_top();
		heap_pop();

		for(size_t i = 0; i < graf[vert.nod].muchii.size(); i++)
		{
			int destinatie = graf[vert.nod].muchii[i].nod;
			int cost = graf[vert.nod].muchii[i].cost;

			if(graf[destinatie].dist > vert.cost + cost)
			{
				graf[destinatie].dist = vert.cost + cost;
				heap_replace(destinatie, graf[destinatie].dist);
			}
		}
	}
}

int main()
{
	std::ifstream fin("dijkstra.in");
	std::ofstream fout("dijkstra.out");
	if(!fin.is_open() || !fout.is_open())
		return -1;

	int a = 0, b = 0, c = 0, n = 0, m = 0;
	fin >> n >> m;

	for(int i = 0; i < m; i++)
	{
		fin >> a >> b >> c;
		graf[a - 1].muchii.push_back(Pair(b - 1, c));
	}

	dijkstra(n, 0);

	for(int i = 1; i < n; i++)
		fout << (graf[i].dist == COST_MAX ? 0 : graf[i].dist) << ' ';

	fout << '\n';

	return 0;
}