#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Edge {
	int from, to, weight;
};

struct Node {
	int vertex, weight;
};

class Graph
{
public:
	vector<vector<Edge>> adjList;

	Graph(vector<Edge> const &edges, int N)
	{
		adjList.resize(N);
		for (Edge const &edge : edges)
		{
			adjList[edge.from].push_back(edge);
			//adjList[edge.to].push_back(edge);
		}
	}
};

void print_route(vector<int> const &prev, int i)
{
	if (i < 0)
		return;

	print_route(prev, prev[i]);
	cout << i << " ";
}

struct comp
{
	bool operator()(const Node &lhs, const Node &rhs) const
	{
		return lhs.weight > rhs.weight;
	}
};
void shortestPath(Graph const& graph, int source, int N)
{
	priority_queue<Node, vector<Node>, comp> min_heap;
	min_heap.push({ source, 0 });

	vector<int> dist(N, INT_MAX);

	dist[source] = 0;

	vector<bool> done(N, false);
	done[0] = true;

	//vector<int> prev(N, -1);
	while (!min_heap.empty())
	{
		Node node = min_heap.top();
		min_heap.pop();

		int u = node.vertex;

		for (auto i : graph.adjList[u])
		{
			int v = i.to;
			int weight = i.weight;

			if (!done[v] && (dist[u] + weight) < dist[v])
			{
				dist[v] = dist[u] + weight;
		//		prev[v] = u;
				min_heap.push({ v, dist[v] });
			}
		}
		done[u] = true;
	}

	for (int i = 1; i < N; ++i)
	{
		cout << dist[i] << " ";
	}
}




int main()
{
	// initialize edges as per above diagram
	vector<Edge> edges =
	{
		{1, 2, 0}, {1, 3, 2}, {1, 5, 5}, {2, 4, 4}, {5, 6, 8},
		{6, 7, 1}//, {4, 1, 1}, {4, 2, 8}, {4, 3, 2}
	};

	// Number of nodes in the graph
	int N = 8;

	// construct graph
	Graph graph(edges, N);

	shortestPath(graph, 5, N);
	int _; cin >> _;
	return 0;
}