/**
	Най-къси пътища в DAG от даден стартов връх s (чрез топологично сортиране)
*/

#include <vector>
#include <algorithm>
#include <iostream>
#define Inf 2000000000
using namespace std;

typedef pair <int, int> pr;

const int n = 8;

vector <pr> graph[n] = {
	{ pr(1, 1), pr(3, 3), pr(4, 5) },
	{ pr(2, 2), pr(5, 2) },
	{},
	{ pr(6, 10) },
	{ pr(7, 2) },
	{},
	{ pr(7, 1) },
	{ pr(5, 5) }
};

int topo_order[n];
int idx;

int dist[n];
int parent[n];
bool visited[n];

void Topo_visit(int u)
{
	visited[u] = true;
	for (pr e : graph[u])if (!visited[e.first])Topo_visit(e.first);
	topo_order[idx--] = u;
}

void Topo_sort() // друг вид топологично сортиране
{
	idx = n - 1;
	for (int i = 0; i < n; i++) visited[i] = 0;;
	for (int i = 0; i < n; i++) if (!visited[i]) Topo_visit(i);
}

void DAG_Shortest_paths(int s)
{
	Topo_sort();

	for (int i = 0; i < n; i++){ dist[i] = Inf; parent[i] = -1; }
	dist[s] = 0;

	for (int i = 0; i < n; i++)
	{
		int u = topo_order[i];

		if (dist[u] != Inf) for (pr e : graph[u])
		{
			int v = e.first, w = e.second;
			if (dist[v] > dist[u] + w){ dist[v] = dist[u] + w; parent[v] = u; }
		}
	}
}

int main()
{
	DAG_Shortest_paths(0);

	for (int i = 0; i < n; i++) if (dist[i] != Inf)cout << dist[i] << " "; else cout << "INF ";
	cout << endl;

	return 0;
}