야쿠르트 아줌마 야쿠르트 주세요

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

요약

가중 무방향 그래프에서 열 개의 판매 지점을 순서대로 방문하는 규칙과 내 시작 정점이 주어질 때, 아주머니보다 늦지 않게 도착할 수 있는 판매 정점 중 가장 작은 번호를 구한다.

난이도: 보통10점 중 7점
유형: 최단 경로, 그래프, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

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

야쿠르트 아줌마는 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을 출력한다.

예제3

예제 1

입력

5 5
1 2 1
1 4 1
2 3 1
2 3 1
3 4 1
1 2 3 4 5 1 2 3 4 5
5

예상 출력

-1

예제 2

입력

6 5
1 2 1
2 3 10
3 4 100
4 5 1000
5 6 10000
1 2 1 2 1 2 6 5 4 3
6

예상 출력

예제 3

입력

11 15
6 1 76
4 3 715
7 6 89
11 5 55
7 9 847
8 5 663
3 4 961
2 8 638
1 9 839
3 7 723
6 1 398
3 2 84
8 1 159
10 3 943
6 4 556
1 2 3 4 5 6 7 8 9 10
10

예상 출력