20160번 - 야쿠르트 아줌마 야쿠르트 주세요

야쿠르트를 외치며 잠에서 깼다. 오늘은 야쿠르트로 하루를 시작하려고 한다.

야쿠르트 아줌마는 10개의 지점을 최단 시간으로 이동하며 들리신다. 각 지점에서 야쿠르트 아줌마보다 같거나 더 일찍 도착한 사람에게 야쿠르트를 팔고 바로 다음 지점으로 출발하신다. 각 지점은 정점 위에 있고 지정된 차례에만 야쿠르트를 판매한다. 야쿠르트를 파는 데 지연되는 시간은 없으며, 오직 이동 시에만 해당 도로의 가중치만큼 시간이 지연된다.

야쿠르트 아줌마는 10개의 지점을 순서대로 방문하며, 10개의 지점 중 첫 번째 지점에서 출발한다. 만약 i번째 지점에서 i+1번째 지점으로 이동 가능한 경로가 없다면 i+2지점으로 이동하신다. i+2로 갈 수 없으면 i+3, i+4...(≤ V)로 이동하신다.

내가 출발하는 시간과 야쿠르트 아줌마가 출발하는 시간은 같다.

내가 출발하는 정점 번호와 야쿠르트 아줌마의 동선을 알려주면 어느 지점으로 가야 야쿠르트를 살 수 있을지 알려줘!!

첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다.

그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ u, v ≤ V) 사이에 가중치가 w(1 ≤ w ≤ 100,000)인 도로가 존재한다는 뜻이다. 정점 사이에는 여러 개의 간선이 존재할 수도 있음에 유의한다.

E+2번째 줄에는 야쿠르트 아줌마가 야쿠르트를 파는 10개 지점의 정점 번호가 주어진다. E+3번째 줄에는 내가 출발하는 정점 번호가 주어진다.

야쿠르트를 살 수 있는 정점이 여러 개라면 그 중 가장 작은 정점 번호를 출력한다.

야쿠르트를 살 수 없다면 -1을 출력한다.