상수도관 건설

21XX년, 인류는 마침내 화성 이주 계획을 시작했다. 화성 이주 제1진에 선발된 당신은 화성 행정 중앙국(the Administrative Center of Mars)에 배속되어 화성에서 일어나는 여러 문제를 처리하고 있다. 행정 중앙국의 가장 큰 당면 과제는 자립적인 수요와 공급의 순환을 확보하는 것이다. 달에서 지원 물자가 도착하기까지는 몇 달 단위의 시간이 걸리므로, 기본적으로 화성 내의 수요는 화성 안에서 해결해야 한다. 게다가 순환 시스템을 확립할 때까지는 자원을 최대한 아껴야 한다.

행정 중앙국은 극지에서 얼음 채굴을 시작했다. 햇빛으로 이를 녹여 물로 각 기지에 공급하는 것이 최종 목표다. 첫 단계로, 수원이 있는 기지에서 두 주요 기지까지 이어지는 송수관을 부설하기로 했다. 또한 현재 시점에서는 몇몇 기지와 그 기지들을 잇는 도로 외에는 개척되지 않았고, 미개척지에 송수관을 부설하려면 막대한 비용과 연료가 들기 때문에 도로를 따라 송수관을 부설하기로 했다. 게다가 기술상의 제약 때문에 그들의 송수관에서는 물이 항상 한 방향으로만 흐른다.

당신의 일은 이러한 조건 아래에서 송수관 부설에 드는 비용을 최소로 하는 프로그램을 작성하는 것이다.

입력은 여러 데이터 세트로 구성된다.

데이터 세트의 첫 줄은 5개의 정수로 이루어진다. 이들은 순서대로 화성에 존재하는 기지의 수 n (3 ≤ n ≤ 100), 기지들을 잇는 도로의 수 m (2 ≤ m ≤ 1000), 수원이 되는 기지의 번호 s, 송수관의 목적지가 되는 두 주요 기지의 번호 g1, g2를 나타낸다. 기지의 번호는 1부터 n까지의 정수로 나타낸다. s, g1, g2는 서로 다르다.

이어지는 m개의 줄에는 송수관을 부설할 수 있는 도로의 정보가 주어진다. 각 줄은 어떤 두 기지 사이의 도로 정보를 나타내며, 3개의 정수 b1, b2, c (1 ≤ c ≤ 1000)로 이루어진다. 여기서 b1, b2는 도로의 시작 기지와 끝 기지의 번호를 나타내며, 이들은 서로 다르다. c는 기지 b1에서 기지 b2로 향하는 송수관을 부설하는 데 드는 비용이다.

모든 데이터 세트에 대해 수원에서 목적지까지 물을 공급하는 경로는 항상 존재한다고 가정해도 좋다. 또한 어떤 두 기지 사이에는 많아야 하나의 도로만 존재하므로, 비용 정보는 각 방향에 대해 많아야 한 번만 주어진다.

입력의 끝은 공백 문자로 구분된 5개의 0이 포함된 줄로 나타낸다.

각 데이터 세트에 대해 송수관을 부설하는 비용의 최솟값을 한 줄에 출력하시오.