[BOJ/백준] 2982 국왕의 방문

import heapq
import sys

def dijkstra(S,E,TERM):
    INF = float('inf')
    distance_list = [INF]*(N+1)
    distance_list[S] = TERM
    node_list = []
    heapq.heappush(node_list,(TERM,S))

    while node_list:
        cur_time,cur_node = heapq.heappop(node_list)

        for next_node in graph[cur_node]:
            if time_spend_list.get((cur_node,next_node)) and time_spend_list[(cur_node,next_node)][0]<=cur_time<=time_spend_list[(cur_node,next_node)][1]:
                spend_time = time_spend_list[(cur_node,next_node)][1] + graph[cur_node][next_node]
            else:
                spend_time = cur_time + graph[cur_node][next_node]
            
            if distance_list[next_node] > spend_time:
                distance_list[next_node] = spend_time
                heapq.heappush(node_list,(spend_time,next_node))

    return distance_list


input = sys.stdin.readline

N,M = map(int,input().split())

start_point,end_point,king_term,G = map(int,input().split())

king_visit_list = list(map(int,input().split()))


graph = [{} for _ in range(N+1)]

for _ in range(M):
    x,y,times = map(int,input().split())

    graph[x][y] = min(graph[x].get(y,float('inf')),times)
    graph[y][x] = min(graph[y].get(x,float('inf')),times)



time_spend_list = {}

king_time = 0
for ind in range(G-1):
    start,ends = king_visit_list[ind],king_visit_list[ind+1]
    time_spend_list[(start,ends)] = (king_time,king_time+graph[start][ends])
    time_spend_list[(ends,start)] = (king_time,king_time+graph[start][ends])
    king_time += graph[start][ends]


result = dijkstra(start_point,end_point,king_term)


print(result[end_point]-king_term)