import sys
input = sys.stdin.readline
from collections import deque
import heapq
INF = sys.maxsize
N,M,X = map(int,input().split())
graph = [[] for i in range(N+1)]
dij = [[INF]*(N+1) for i in range(N+1)]
for i in range(M):
x1,x2,t = map(int,input().split())
graph[x1].append((x2,t))
def Dijkstra(start):
hq = []
heapq.heappush(hq,(0,start))
while hq:
w,now = heapq.heappop(hq)
if dij[start][now] <= w:
continue
dij[start][now] = w
for i in graph[now]:
x1,w1 = i
heapq.heappush(hq,(w1+w,x1))
for i in range(1,N+1):
Dijkstra(i)
result = 0
for i in range(1,N+1):
result = max(dij[i][X]+dij[X][i],result)
print(result)
노드수는 엄청 많은데 (최대 1000개) 간선의 수는 몇개 없는걸 보고 다 익스트라를 써야되는건가? 라고 생각은 했는데, 다 익스트라 코드쓰기가 귀찮아서 쉽고 편한 플로이드를 썼는데 당연하게도 시간초과가 나왔다 ㅋㅋ
결국 그냥 다 익스트라 N번 때리고 정답을 구했다.
오늘의 교훈) 문제의 조건을 잘 읽고 적절한 알고리즘을 선택하자