늦은 파티

오늘 밤 연회가 끝나면, 새로 사귄 F명의 친구와 함께 연회장을 나와 호텔로 걸어 돌아간다. 친구들과 최대한 오래 이야기하고 싶지만, 안타깝게도 모두 같은 호텔에 묵는 것은 아닐 수 있다.

본인을 포함한 모든 사람은 각자의 호텔로 돌아가는 최단 경로 중 하나를 따라간다.

파리는 0번부터 N − 1번까지 번호가 붙은 N개의 교차로와 두 교차로를 잇는 S개의 거리로 이루어져 있다. 거리는 물론 양방향으로 걸을 수 있다. 모든 호텔은 교차로에 있으며 연회장에서 갈 수 있다. 연회는 0번 교차로에서 열린다.

입력은 여러 줄로 이루어지며, 각 줄은 하나의 공백으로 구분된 정수들로 구성된다.

• 첫째 줄에는 세 정수 N, S, F가 주어진다.
• 다음 S개 줄에는 각각 세 정수 i, j, t가 주어지며, 교차로 i와 j 사이에 걸어서 지나는 데 t분이 걸리는 거리가 있음을 나타낸다.
• 마지막 줄에는 사람들이 묵는 호텔의 교차로를 나타내는 F + 1개의 정수가 주어진다. 첫 번째는 본인의 호텔이고, 나머지는 친구들의 호텔이다.

출력은 한 줄로 이루어지며, 그 내용은 친구 한 명 이상과 동행할 수 있는 최장 시간(분)을 나타내는 정수이다.

• 1 ≤ N ≤ 100 000
• 0 ≤ S ≤ 300 000
• 0 ≤ F ≤ 10 000
• 1 ≤ t ≤ 1 000 000