잼 공장

그루는 새 사업을 시작하려고 지하 실험실에서 잼을 만든다. 미니언들은 거대한 통 여러 개에서 과일을 으깬다. 잼을 만들려면 이 통을 굵은 배관으로 이어야 한다. 지난번 잼이 실패한 뒤, 그루는 과일 두 종류를 섞어 새로운 잼을 만들려고 한다.

통 두 개를 배관으로 잇는 비용이 주어진다. 통 v1과 통 v2를 병입기로 이어지는 통 vd에 연결하는 가장 싼 방법을 찾아라. v1의 과일과 v2의 과일이 모두 vd에 도달해야 한다. 두 경로는 배관 일부를 함께 써도 되고, 그러지 않아도 된다. 함께 쓰는 배관의 비용은 한 번만 낸다. 경우에 따라 두 통을 모두 vd에 연결하지 못할 수도 있다.

그림은 예시 두 개를 보여 준다. 예시마다 통 5개와 배관 후보 5개가 있고, 통 1과 통 2를 병입기로 이어지는 통 5에 연결해야 한다. 왼쪽 예시는 배관 비용이 모두 1이라 최소 비용이 3이고, 배관 1-4, 2-4, 4-5를 놓으면 된다(실선). 오른쪽 예시는 통 1과 통 4를 잇는 배관의 비용이 4로 올랐다. 이때는 최소 비용이 4이고, 배관 1-3, 3-5, 2-4, 4-5를 놓으면 된다(실선).

입력은 꽤 클 수 있다. 한 테스트 케이스에 통이 수백 개, 배관 후보가 수천 개인 경우가 있으므로, 가능한 연결 방식을 모두 확인하는 방법은 제한 시간 안에 끝나지 않는다.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 다섯 개가 주어진다. 통의 개수 v, 배관 후보의 개수 p, 연결해야 하는 두 통의 번호 v1과 v2, 병입기와 이어진 통의 번호 vd이다.

이어서 p개의 줄에 정수 세 개 vx, vy, c가 주어진다. 통 vx와 통 vy를 잇는 배관의 비용이 c라는 뜻이다. 배관은 양방향으로 쓸 수 있다. 통의 번호는 1부터 v까지이고, 비용은 음이 아닌 정수이다. 같은 통 쌍이 여러 번 주어질 수 있고, vx와 vy가 같은 줄도 있을 수 있다.

마지막 테스트 케이스 다음 줄에는 0 하나만 주어진다.

각 테스트 케이스마다 최소 비용을 한 줄에 다음 형식으로 출력한다.

Cost of connecting v1 and v2 to vd is c

v1, v2, vd는 입력으로 주어진 번호이고 c는 최소 비용이다. 두 통 중 하나라도 vd에 연결할 수 없으면 다음 줄을 대신 출력한다.

Cannot connect v1 and v2 to vd