import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미

n, m = map(int, input().split()) # 노드의 개수, 간선의 개수
start = int(input()) # 시작 노드
graph = [[] for i in range(n+1)]
visited = [[False] * (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 get_smallest_node() : # 방문하지 않은 노드 중에 가장 최단 거리가 짧은 노드의 번호
    min_value = INF
    index = 0
    for i in range(1, n+1) :
        if not visited[i] and distance[i] < min_value  :
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    # 시작 노드 초기화
    distance[start] = 0
    visited[start] = True
    for j in graph[start]: distance[j[0]] = j[1]

    # 시작 노드를 제외한 전체 n-1개 노드 반복
    for i in range(n-1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서 방문 처리
        now = get_smallest_node()
        visited[now] = True
        # 현재 노드와 연결된 다른 노드 확인
        for j in graph[now]:
            cost = distance[now] + j[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[j[0]]:
                distance[j[0]] = cost

dijkstra(start) # 다익스트라 알고리즘 수행

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

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미

n, m = map(int, input().split()) # 노드의 개수, 간선의 개수
start = int(input()) # 시작 노드
graph = [[] for i in range(n+1)]
visited = [[False] * (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 : continue
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                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])

INF = int(1e9)

n = int(input())
m = int(input())

graph = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b : graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아 그 값으로 초기화
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1, n+1) :
    for a in range(1, n+1) :
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과 출력
for a in range(1, n+1) :
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print("INFINITY", end=" ")
        else : print(graph[a][b], end= " ")

INF = int(1e9)
n, m = map(int, input().split())
graph = [[INF] * (n+1) for _ in range(n+1)]

for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

for _ in range(m):
    a, b= map(int, input().split()) # 비용은 1이라고 주어짐
    graph[a][b] = 1
    graph[b][a] = 1

X, K = map(int, input().split())

for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

distance = graph[1][K] + graph[K][X]

if distance >= INF : print('-1')
else: print(distance)

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9)

n, m, start = map(int, input().split())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
    x, y, z = map(int, input().split())
    graph[x].append((y, z))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist : continue

        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)

count = 0
max_dist = 0
for d in instance:
    if d != INF :
        count += 1
        max_dist = max(max_dist, d)

print(count-1, max_dist)