BOJ_1753

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef struct {
	int start, end, value;
}vertex_value;
vertex_value vertex_value_in()
{
	int start, end, value;
	std::cin >> start >> end >> value;
	return{ start, end, value };
}
template <typename type> std::vector<type>  vector_in(long count)
{
	std::vector<type> vector;
	for (long i = 0; i < count; i++)
		vector.push_back(vertex_value_in());
	return vector;
}
int main(int argc , char * argv[])
{
	int vertex_max, line_max ,vertex_start;
	std::cin >> vertex_max >> line_max >> vertex_start;
	std::vector<vertex_value> vector = vector_in<vertex_value>(line_max);
	std::vector<int> vector_value(vertex_max+1, -1);
	vector_value[vertex_start] = 0;
	while (1)
	{
		vertex_value vertex = { 0, 0, 11 };
		for (int vertex_ = 0; vertex_ < line_max; vertex_++)
			if (vector_value[vector[vertex_].start] + 1 && !(vector_value[vector[vertex_].end] +1) && vector[vertex_].value < vertex.value)
				vertex = vector[vertex_];
		if (vertex.value == 11)
			break;
		vector_value[vertex.end] = vector_value[vertex.start] + vertex.value;
	}
	for (int i = 1; i <= vertex_max; i++)
		if (vector_value[i] + 1)
			std::cout << vector_value[i] << std::endl;
		else
			std::cout << "INF" << std::endl;

	return 0;
}