#include <fstream>
#include <vector>
#include <limits>
#include <utility>
#include <queue>

std::ifstream f("dijkstra.in");
std::ofstream g("dijkstra.out");

constexpr int INF = std::numeric_limits<int>::max();
constexpr int MAX = 50001;
constexpr int source = 1;

int numNodes, numArcs;

// first - neighbour 'name', second - distance
std::vector<std::pair<int, int>> graph[MAX];
std::vector<int> dist(MAX, INF);

bool isInQueue[MAX] = { false };

auto comp = [](int x, int y) -> bool { return dist[x] > dist[y]; };

std::priority_queue<int, std::vector<int>, decltype(comp)> nodes(comp);

void Read()
{
	f >> numNodes >> numArcs;

	int i, nod1, nod2, cost;
	
	for (i = 1; i <= numArcs; ++i) {
		f >> nod1 >> nod2 >> cost;

		graph[nod1].emplace_back(nod2, cost);
	}
}

void Init()
{
	for (int i = 1; i <= numNodes; ++i) 
		if (i != source) 
			dist[i] = INF;

	dist[source] = 0;

	nodes.emplace(source);
	isInQueue[source] = true;
}

void Dijkstra()
{  
	while (!nodes.empty()) {
		int currentNode = nodes.top();

		for (const auto& neighbour : graph[currentNode]) 
			if (dist[currentNode] + neighbour.second < dist[neighbour.first]) {
				dist[neighbour.first] = dist[currentNode] + neighbour.second;

				if (!isInQueue[neighbour.first]) {
					nodes.emplace(neighbour.first);
					isInQueue[neighbour.first] = true;
				}
			}

		nodes.pop();
		isInQueue[currentNode] = false;
	}
}

void Print()
{
	/*
	for (int i = 1; i <= numNodes; ++i) {
		for (const auto& pair : graph[i]) {
			g << pair.first << ' ' << pair.second << "   ";
		}
		g << '\n';
	}
	*/

	for (int i = 1; i <= numNodes; ++i) 
		if (i != source) 
			g << ((dist[i] == INF) ? 0 : dist[i]) << ' ';
}

int main(int argc, char * argv[])
{
	Read();
	Init();
	Dijkstra();
	Print();

	return 0;
}