16211번 - 백채원 서브태스크

대구과학고의 인기 아이돌 그룹 D.O.G.의 에이스이자(그의 <What is Love?> 댄스 영상을 찾아보아라.), 3천 명을 아득히 넘는 열혈 추종자를 보유한 슈퍼스타 백채원은 오늘 외박을 신청하고 집에 가려 한다. 하지만 백채원의 열혈 추종자 중 몇 명은 이 사실을 듣고 백채원을 만나러 가기로 한다.

편의상 우리나라에는 N개의 지점이 있고, 이 지점들 중 몇 쌍을 양방향으로 잇는 M개의 도로들로 모든 지점들이 직·간접적으로 연결되어 있다고 생각하자. 각 지점은 1번에서 N번까지로 번호가 붙어 있다. 각 도로의 길이는 다를 수도 있다. 대구과학고는 1번 지점에 있으며, 2번에서 N번까지의 모든 지점에 백채원의 집이 하나씩 있다. 백채원은 1번 지점에 있는 대구과학고에서 백채원의 집들 중 하나로 이동하려 한다(몇 번 지점의 집으로 이동할지는 미리 생각해 두었다). 또한, 백채원의 추종자 K명은 1번이 아닌 서로 다른 K개의 지점에 살고 있는데, 이들은 백채원이 대구과학고에서 출발하자마자 각자 전략을 새워서 백채원을 만나러 갈 것이다.

당신은, 추종자들이 어떠한 전략을 세워서 백채원을 찾으려 하더라도 절대 백채원이 추종자 중 누구에게도 붙잡히지 않고 이동할 수 있기 위해서는, 백채원이 몇 번 지점에 있는 집으로 출발했어야 할지 궁금해졌다. 가능한 지점 번호를 모두 출력하는 프로그램을 작성해 보자.

단, 백채원은 대구과학고가 있는 1번 지점에는 살지 않는다. 또한, 추종자들과 백채원은 항상 도로 위에서 등속력운동을 하며, 모두 같은 속력으로 이동한다고 가정한다. 백채원이 집이 있는 지점에 도착하는 순간 추종자와 만나도, 백채원은 추종자에게 붙잡힌 것으로 생각한다.

첫째 줄에는 우리나라에 있는 지점의 수 N과 도로의 수 M, 백채원의 추종자의 수 K가 차례대로 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ M ≤ 500,000, 1 ≤ K ≤ N-1)

둘째 줄부터 M개의 줄에 차례대로 M개의 각 도로가 잇는 지점의 번호 A, B와 이 도로를 통해 두 지점을 오가는 데에 걸리는 시간 T가 주어진다. (1 ≤ A, B ≤ N, 1 ≤ T ≤ 10,000, A ≠ B, 같은 도로가 두 번 주어지지 않는다.)

마지막 줄에는 백채원의 추종자들이 사는 지점의 번호를 나타내는 서로 다른 자연수 P₁, …, P_K가 공백을 사이에 두고 주어진다. (2 ≤ P_i ≤ N)

백채원의 집이 될 수 있는 지점의 번호들을 한 줄에 공백을 사이에 두고 오름차순으로 출력하라.

만약 그런 지점이 하나도 없다면, 대신 정수 0을 출력한다.

백채원은 1번 지점에 집을 가지고 있지 않다는 점에 유의하라.

1 ≤ N ≤ 200, 1 ≤ M ≤ 1,000, K = 1을 만족하고, 각 도로를 이동하는 데 시간 1이 걸린다.

1 ≤ N ≤ 200, 1 ≤ M ≤ 1,000을 만족한다.

1 ≤ N ≤ 2,000, 1 ≤ M ≤ 10,000을 만족한다.

문제에 제시된 것 이외의 다른 제약은 없다.