안전한 유선 전화망
시간 제한2초메모리 제한256 MB
출발지와 목적지가 아닌 취약 건물을 거치지 않으면서 모든 건물을 가장 저렴하게 연결합니다.
문제
RMRCity 시장은 큰 재난으로 도시가 외부와 끊겼을 때 쓸 비상용 유선 전화망을 만들려고 한다. 도시의 어떤 건물 쌍은 전화선으로 직접 이을 수 있고, 시청 기술자들이 그런 쌍마다 연결 비용을 미리 산정해 두었다.
모든 건물을 잇는 가장 싼 전화망을 찾되, 다음 보안 조건을 지켜야 한다. 건물 A에서 건물 B로 건 통화는 전화망 안의 아무 단순 경로나 따라 전달될 수 있다. 단순 경로는 같은 건물을 두 번 지나지 않는 경로다. 도시에는 중범죄 전과자가 한 명 이상 사는 위험 건물이 몇 개 있다. 시장은 위험 건물로 걸려 온 통화만 그 건물에 닿기를 원한다. 즉 건물 A에서 건물 B로 가는 통화는 A도 B도 아닌 위험 건물 C를 거쳐서는 안 된다.
입력
입력은 테스트 케이스 하나로 이루어진다.
첫째 줄에 정수 , , 가 주어진다. 은 건물 수로 이고, 은 직접 이을 수 있는 건물 쌍의 수로 이며, 는 위험 건물의 수로 이다. 건물 번호는 부터 까지다.
둘째 줄에 위험 건물의 번호인 서로 다른 정수 개가 주어진다. 가 이면 둘째 줄은 빈 줄이다.
이어지는 개 줄에는 각각 정수 , , 가 주어져 놓을 수 있는 전화선 하나를 나타낸다. 와 는 그 전화선이 잇는 서로 다른 두 건물이고 (), 는 연결 비용의 추정값이다 (). 같은 건물 쌍을 잇는 전화선은 이 개 줄에 많아야 한 번 나온다.
출력
보안 조건을 만족하는 가장 싼 전화망의 비용을 출력한다. 그런 전화망이 없으면 impossible을 출력한다.