문제
한신이는 젊고, 똑똑하고 매우 유명한 정치인이다. 그럼에도 그는 여전히 자신의 성공을 위해서도 인간관계는 중요한것이라고 믿고있다. 다음달에 열릴 국회의원선거에서 한신이는 자신의 당이 반드시 이기길 희망한다. 그러기 위해서 최고의원의 지지가 필요하다.
이 최고의원의 지지를 받기위해 한신이는 전략을 세웠다. 그는 그 최고의원을 직접적으로 만날수 없다면 그를 알고있는 인맥을 이용하여 만날것이다. 이것을 위해서 우선 정치인들의 친밀도를 조사하였는데 친밀도를 다음 4단계로 나누어서 기록해놓았다.
최측근 [1] / 측근 [2] / 비즈니스관계 [3] / 지인 [4]
[두 사람의 관계는 이 4가지 경우중 반드시 해당되며, 적(enemy)는 존재하지 않는다.]
한신이는 지인보다는 최측근 친구에게 소개받기 원한다. 그래서 최고의원을 만나기까지의 인맥간 친밀도의 합을 최소화하고 싶어한다.
N명의 정치인 명단으로부터 그들의 인맥 친밀도가 주어진다. 정치인 리스트를 보고 한신이가 최고의원을 만나기까지의 친밀도의 합 중에서 가장 작은 값을 구하면 된다.
# 9694
import sys
input = lambda : sys.stdin.readline().strip()
INF = int(1e9)
import heapq
t = int(input())
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]))
dist_now[i[0]] = dist_now[now] + [i[0]]
for i in range(1, t+1):
n, m = map(int, input().split())
graph = [[] for _ in range(m)]
distance = [INF] * (m)
dist_now = [[i] for i in range(m)]
for _ in range(n):
a, b, c = map(int, input().split())
graph[a].append((b, c))
graph[b].append((a, c))
dijkstra(0)
if dist_now[m-1] == [m-1]:
dist_now[m-1] = [-1]
print("Case #" + str(i) + ": ", end = "")
print(*dist_now[m-1])