import heapq

# 오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
	h = []
	result = []
	# 모든 원소를 차례대로 힙에 삽입
	for value in iterable:
		heapq.heappush(v, value)
	for i in range(len(h)):
		result.append(heap.heappop(h))
	return result

result = heapsort([1, 3, 5, 7, 8, 2, 4, 6, 8, 0])
print(result)

# 실행 결과
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# 내장된 병합, 퀵 정렬 알고리즘과 같은 수준의 시간 복잡도를 보여줍니다. 
# 따라서 최악의 경우에도 동일한 시간 복잡도를 보장해줍니다.

import heapq

# 내림차순 힙 정렬(Heap Sort)
def heapsort(iterable):
	h = []
	result = []
	# 모든 원소를 차례대로 힙에 삽입
	for value in iterable:
		heapq.heappush(v, -value) # 기본적으로 파이썬은 최대힙은 지원하지 않습니다. 
	for i in range(len(h)):
		result.append(-heap.heappop(h))
	return result

result = heapsort([1, 3, 5, 7, 8, 2, 4, 6, 8, 0])
print(result)

# 실행 결과
# [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
# 무한을 의미하는 값으로 10억을 설정

# Node 개수, 간선의 개수를 입력받기
n, m = map(int, input().stdin())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결된 정보 리스트
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블
distance = [INF] * (n + 1)
# 해당 예제는 기존 방문 테이블이 따로 존재하지 않음

# 간선 정보를 입력 받는다.
for _ in range(m):
	# a번 노드에서 b번 노드로 가는 비용이 c 라는 의미
	a, b, c = map(int, input().split())
	graph[a].append((b, c))

def dijkstra(start):
	q = []
	# 시작 위치 설정
	heapq.heappush(q, (0, start))
	distance[start] = 0
	while q:
		dist, now = heapq.heappop(q):
		if distance[now] < dist: # 현재 지정된 노가 이미 처리되어 dist 값보다 작다면 처리 안함
			continue
		# 인접 노드 탐색
		for i in graph[now]:
			cost = dist + i[0]
			# 현재 해당 노드까지 가는데 걸리는 비용이 작은 경우 갱신
			if cost < distance[i[0]]
				distance[i[0]] = cost
				# 갱신의 핵심인 priority que 사용
				heapq.heappush(q, (cost, i[0]))

dijkstra(start)

for i in range(1, n + 1):
	if distance[i] = INF:
		print("INFINITY")
	else:
		print(distance[i])

#include <std/bitsc++.h>
#define INF 1e9

using namespace std;

int n, m, start;
vector<pair<int, int>> graph[100001];
int d[100001];

void dijkstra(int start)
{
	priority_queue<pair<int, int>> pq;
	pq.push({0, start});
	d[start] = 0;
	while(!pq.empty())
	{
		int dist = -pq().first;
		int now = pq.top().second;
		pq.pop();
		if (d[now] < dist)
			continue ;
		if (cost < d[graph[now][i].first])
		{
			d[graph[now][i].first] = cost;
			pq.push(make_pair(-cost, graph[now][i].first));
			// 해당 라이브러리의 경우 파이선과 반대로 최대 힙으로 구성되어 있어 값을 음수로 집어 넣습니다. 
		}
	}
}

int main(void)
{
	cin >> n >> m >> start;

	for (int i = 0;, i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({b, c});
	}

	fill(d, d + 10001, INF);

	dijkstra(start);

	for (int i = 1; i <= n; i++)
	{
		if (d[i] == INF)
			cout << "INFINITY" << '\n';
		else
			cout << d[i] << '\n';
	}
}