문제

연예인 김영광을 너무 닮아서 길거리에서 매번 사진이 찍히는 지헌이는 사람들에게 노출되는 것을 매우 꺼려한다. 하지만 친구인 성하와 약속을 하면 성하는 매번 늦기 때문에 길거리에 나온 지헌이는 매번 성하를 기다린다. 약속 장소에서 성하에게 전화를 하면 매번 “가는 중” 이라는 대답만 듣고 기다리는 동안 길거리에서 사람들에게 사진을 찍히는 지헌이는 스트레스를 심하게 받고 있다. 참지 못한 지헌이는 성하의 핸드폰을 해킹하여서 항상 어디 있는지 알 수 있게 되었다.

스트레스가 심해진 지헌이는 성하와의 약속 장소를 바꾸려고 한다. 그 위치는 다음과 같은 조건을 만족해야 한다. 장소의 번호는 1부터 차례대로 붙어 있다.

1. 지헌이의 출발 위치와 성하의 출발 위치는 새로운 약속 장소가 될 수 없다.
2. 성품도 훌륭한 지헌이는 새로운 약속 장소는 지헌이가 걸리는 최단 시간과 성하가 걸리는 최단 시간의 합이 최소가 되도록 하고 싶다.
3. 지헌이가 더 늦게 도착하면 성하에게 안좋은 소리를 들을 것이 뻔하기에, 1번과 2번 조건을 만족하는 장소 중에서도 지헌이가 성하보다 늦게 도착하는 곳은 약속 장소가 될 수 없다.
4. 위의 세 조건을 모두 만족하는 약속 장소가 여러 곳이 있다면, 그 중에 지헌이로부터 가장 가까운 곳이 최종 약속 장소가 된다. 그런 장소도 여러 곳이 있다면, 그 중에 번호가 가장 작은 장소가 최종 약속 장소가 된다.

# 17270
import sys
input = lambda : sys.stdin.readline().strip()
INF = sys.maxsize

import heapq
v, m = map(int, input().split())
graph = [[] for _ in range(v+1)]
distance = [INF] * (v+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
    
j, s = map(int, input().split())

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]))
                
dijkstra(j)
distance_j = [i for i  in distance]
distance = [INF] * (v+1)

dijkstra(s)
distance_s = [i for i in distance]

location = INF    # 약속 장소
total_time = INF  # 시간의 합
last_time_j = INF # 현재 약속장소의 지헌 시간

for i in range(1, v+1):    
    if i == j or i == s:
        continue
    else:
        time_now = distance_j[i] + distance_s[i]
        if time_now > total_time:
            continue
        elif time_now < total_time:
            total_time = time_now
            last_time_j = INF
            
        if distance_j[i] > distance_s[i]:
            if last_time_j == INF:
                location = INF
            continue
            
        if distance_j[i] < last_time_j:
            location = i
            last_time_j = distance_j[i]
        

if location == INF:
    location = -1
    
print(location)

백준 17270 연예인은 힘들어