수배

경찰관 Acsel에게 위험한 범죄자 Waxel을 붙잡는 긴급한 일을 위해 여러분의 도움이 필요하다. Waxel은 $N$개의 서로 다른 장소로 이루어진 도시 어딘가에 숨어 있다. 장소에는 $1$부터 $N$까지 번호가 매겨져 있으며, 각각 서로 다른 두 장소를 연결하는 $M$개의 양방향 도로가 있다. 그는 오랫동안 어떤 장소 $X$에 머물렀지만(어느 장소인지는 알 수 없다), 이후 일련의 도로를 따라 이동하여 다른 장소 $Y$로 갔다(이 장소도 알 수 없다).

경찰은 Waxel을 목격한 사람들로부터 $K$개의 증언을 수집했다. 따라서 경찰은 Waxel이 $X$에서 $Y$까지 가는 도중 장소 $a_1, a_2, \dots, a_K$를 방문했다는 것을 알고 있다(어떤 $i$에 대해서는 $a_i = X$ 또는 $a_i = Y$일 수도 있다). 하지만 장소들을 어떤 순서로 방문했는지는 알지 못한다. 또한 Waxel은 $X$에서 $Y$까지 가는 도중 이 $K$개의 장소 외에도 더 많은 장소를 방문했을 수 있다.

이제 여러분의 임무는 Waxel이 $X$에서 $Y$까지 가장 짧은 도로의 연속을 따라 이동했다는 조건하에, $Y$일 가능성이 있는 장소를 찾도록 경찰을 돕는 것이다(이는 Waxel이 이동한 도로들의 길이의 합이 가능한 한 작다는 뜻이다.). 증언과 일치하는 최단 경로가 없다면 그러한 장소가 전혀 없을 수도 있다.

채점

여러분의 풀이는 여러 테스트 케이스 그룹으로 테스트된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$5$| 도로는 정확히 $N - 1$개이며, 각각 장소 $1$과 $2$, $2$과 $3$ 등을 연결하고 마지막으로 $N - 1$과 $N$을 연결한다

$2$ |$16$| 모든 장소 쌍 사이에 (반복되지 않는) 도로의 연속이 하나만 존재하며, 그 결과 $M = N - 1$이다

$3$ |$15$| $N,M \leq 100$

$4$ |$17$| $N,M \leq 1\,000$

$5$ |$15$| $N,M \leq 10^5$ 및 $K \leq 5$

$6$ |$32$| 추가 제한 없음

첫 번째 줄에는 다음 세 정수가 주어진다.

• 도시의 장소 수, $N$ ($2 \leq N \leq 2\cdot 10^5$),

• 도시의 도로 수, $M$ ($1 \leq M \leq 2 \cdot 10^5$), 그리고

• 증언의 수, $K$ ($1 \leq K \leq N$).

두 번째 줄에는 Waxel이 방문한 장소를 나타내는 $K$개의 서로 다른 정수 $a_1, \dots, a_K$ ($1 \leq a_i \leq N$)가 주어진다.

다음 $M$개 줄에는 도시의 서로 다른 도로들이 설명된다. $i$번째 줄에는 세 정수 $u_i$, $v_i$ ($1 \leq u_i \not= v_i \le N$), 그리고 $w_i$ ($1 \leq w_i \leq 10^9$)가 주어지며, 이는 $i$번째 도로가 장소 $u_i$과 $v_i$를 연결하고 길이가 $w_i$미터임을 뜻한다. 어떤 두 장소 사이든 일련의 도로를 따라 이동하여 오갈 수 있으며, 모든 장소 쌍 사이를 직접 연결하는 도로는 최대 하나임이 보장된다.

첫 번째 줄에 $Y$일 수 있는 정점의 수를 출력한다. 이 수는 $0$일 수 있음에 유의한다.

두 번째 줄에 $Y$일 수 있는 모든 정점을 출력한다. 이들은 공백으로 구분하여 오름차순으로 출력해야 한다.

예제 $1$에서는 장소 $1,2,4,5$가 Waxel의 가능한 목적지이다. $2$에 도착하기 위해 그는 경로 $5-6-1-2$을 이용할 수도 있었다.

예제 $2$에서는 주어진 정점들을 통과하는 최단 경로가 없다. 따라서 답은 $0$이다.

예제 $3$에서는 가능한 경우가 상당히 많다. 예를 들어 $2$에 도착하기 위해 Waxel은 경로 $6-7-5-3-1-2$을 이용할 수도 있었다.