관광

도시 관광지를 노드, 도로를 양방향 간선으로 모델링한다. 각 도로에는 품질 값이 있고, 경로의 품질은 경로 위 간선 품질의 최솟값이다. 호텔은 노드 1이다. 각 목적지에 대해 노드 1에서 갈 수 있는 경로 중 경로 품질의 최댓값을 출력한다.

첫 줄에 $,$, $가 주어진다. 다음$줄에 간선 $,$, 품질 $(-- \le q \le 100000$)가 주어진다. 다음 $줄에 목적지$ ( e 1$)가 주어진다.

각 목적지에 대해 달성 가능한 최고 경로 품질을 한 줄에 하나씩 출력한다.

\le 500000$, \le 5000000$, \le V-1$