# 해킹
import heapq
import sys
input = sys.stdin.readline
def hacking(n, start):
dist = [sys.maxsize] * (n+1)
dist[start] = 0
q = []
heapq.heappush(q, (0, start))
while q:
time, computer = heapq.heappop(q)
for ntime, ncom in arr[computer]:
total = time + ntime
if dist[ncom] > total:
dist[ncom] = total
heapq.heappush(q, (total, ncom))
result_time = 0
result_com = 0
for x in dist:
if x != sys.maxsize:
result_com += 1
result_time = max(result_time, x)
return [result_com, result_time]
T = int(input())
for _ in range(T):
n, d, c = map(int, input().split())
arr = [[] for _ in range(n+1)]
for _ in range(d):
a, b, s = map(int, input().split())
arr[b].append((s, a))
print(*hacking(n, c))
최단거리, 다익스트라 1. 의존성에 맞춰서 입력을 받는다. (arr[b].append((s, a)) => a가 b를 의존) 2. hacking(n, c) : n개의 컴퓨터 중, c컴퓨터에서 부터 해킹 시작 - start에서 각 컴퓨터까지의 거리를 dist리스트로 표현 - dist를 최소값으로 업데이트 (heapq를 이용) - dist에서 maxsize가 아닌 값들 마다 result_com++, dist에서 해당 거리 값 중 가장 큰 값을 result_time으로 - return [result_com, result_time] 3. 출력
