우주 탐사선

탐사선이 지구(1번 행성)에서 목적지 행성(D번)으로 여행한다. N개의 행성과 M개의 항로(단방향)가 있으며, 각 항로에는 연료 비용이 있다. 일부 행성에는 연료 충전소가 있다.

연료 충전소가 있는 행성을 지나면 남은 연료가 FULL(=100)이 된다. 지구와 목적지도 충전소가 있다고 가정한다. 탐사선이 지구에서 출발할 때 연료는 100이다. 목적지까지 최소 연료를 소모하며 도달하는 방법을 구하시오. 단, 각 구간에서 필요한 연료는 해당 항로 비용이다. 도달 불가능하면 -1을 출력한다.

입력

첫째 줄에 행성 수 N, 항로 수 M, 목적지 D가 주어진다. 둘째 줄에 연료 충전소가 있는 행성 번호들이 주어진다(첫 번째 숫자는 충전소 수). 다음 M줄에 항로 정보 (A B C) — A→B 이동에 연료 C 소모.

• 2 ≤ N ≤ 1,000
• 1 ≤ M ≤ 10,000
• 1 ≤ C ≤ 100
• 지구(1번)와 목적지(D번)는 항상 충전소 보유

출력

최소 연료 소모량을 출력한다. 도달 불가능하면 -1을 출력한다.