링크 : https://www.acmicpc.net/problem/1238
import heapq
from sys import stdin
input = stdin.readline
n, m, x = map(int, input().split())
graph = [ [] for _ in range(n+1) ]
for _ in range(m):
a, b, t = map(int, input().split())
graph[a].append((b, t))
def dijkstra(start):
q = []
distance = [1e9] * (n+1) # 최소 거리가 적힌 배열
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q) # 최소힙 이용
if distance[now] < dist:
continue
for node_index, node_cost in graph[now]:
cost = dist + node_cost
if distance[node_index] > cost:
distance[node_index] = cost
heapq.heappush(q, (cost, node_index))
return distance
result = 0
for i in range(1, n+1): # i는 다익스트라를 시작하는 지점을 의미
go = dijkstra(i)
back = dijkstra(x)
result = max(result, go[x] + back[i])
print(result)