가운데에서 만나기

면접 대비

시간 제한1초메모리 제한512 MB

요약

가중치가 있는 방향 그래프와 K개의 출발 도시가 주어질 때, 각 출발 도시에서 X까지 갔다가 돌아오는 왕복 시간의 최댓값을 최소로 만드는 모든 도시 X를 찾아 오름차순으로 출력한다.

문제

준형이는 내일 친구들을 만나기로 했다. 준형이와 친구들은 서로 다른 도시에 살고 있다.

도시를 연결하는 도로는 일방 통행만 있어서 도시 $A_i$ 에서 도시 $B_i$ 로 가는 시간과 도시 $B_i$ 에서 도시 $A_i$ 로 가는 시간이 다를 수 있다.

준형이와 친구들은 아래 조건을 만족하는 도시 $X$ 를 선택하여 거기서 만나려고 한다.

왕복시간은 자신이 살고 있는 도시에서 도시 $X$ 로 이동하는 시간과 도시 $X$ 에서 다시 자신이 살고 있는 도시로 이동하는 시간을 합한 것이다.
준형이와 친구들이 도로를 이용하여 갈 수 있는 도시만 선택한다.
준형이와 친구들의 왕복시간 들 중 최대가 최소가 되는 도시 $X$ 를 선택한다.
준형이와 친구들이 이동할 수 있는 도시가 최소한 하나 이상이 있음을 보장한다.

도시가 많다보니 계산하기 힘들다. 준형이와 친구들을 대신하여 도시 $X$ 를 알려주자.

첫 번째 줄에는 도시의 개수 $N$ 과 도로의 개수 $M$ 이 주어진다.

두 번째 줄부터 $M + 1$ 줄까지 도시 $A_i$ , 도시 $B_i$ , 도시 $A_i$ 에서 도시 $B_i$ 로 이동하는데 걸리는 시간 $T_i$ 가 공백으로 구분되어 주어진다.

$M + 2$ 줄에는 준형이와 친구들의 총 인원 $K$ 가 주어진다.

$M + 3$ 줄에는 준형이와 친구들이 살고 있는 도시의 번호 $C_i$ 가 공백으로 구분되어 주어진다.

위 조건을 만족하는 도시 $X$ 의 번호를 출력한다. 만약 가능한 도시 $X$ 가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다.

예제 1

입력

예상 출력