3인 통화

코리아 통신회사는 세 사람이 동시에 통화할 수 있는 3인 통화 서비스를 제공한다. 전화망은 여러 스위치와 스위치 사이를 잇는 양방향 링크로 이루어져 있으며, 통화자는 각각 하나의 스위치에 접속한다. 전화망의 모든 스위치는 서로 연결되어 있으므로, 어느 스위치에 접속한 사람도 다른 스위치에 접속한 사람과 통화할 수 있다. 각 링크에는 그 링크를 사용하는 비용이 정해져 있다.

세 통화자가 접속한 스위치가 주어졌을 때, 세 스위치를 모두 연결하는 데 필요한 비용이 최소가 되도록 링크들을 선택해야 한다. 최소 비용과 그때 사용하는 링크들을 출력하는 프로그램을 작성하라.

첫 번째 줄에 두 정수 n과 m이 주어진다. n은 전화망에 있는 스위치의 수이며 1 <= n <= 1000이다. m은 스위치 사이를 잇는 링크의 수이다. 같은 두 스위치를 직접 연결하는 링크는 둘 이상 존재하지 않는다. 스위치에는 1번부터 n번까지 번호가 붙어 있다.

다음 m개의 줄에는 각 링크의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 링크로 연결된 두 스위치의 번호와 그 링크를 사용하는 비용이 주어진다. 비용은 양의 정수이며 100보다 작다.

마지막 줄에는 세 통화자가 접속한 스위치 번호 세 개가 주어진다. 세 번호는 모두 다르다.

첫 번째 줄에 세 통화자를 최소 비용으로 연결할 때의 총비용과, 선택한 링크의 수를 출력한다.

그다음 줄부터 선택한 각 링크의 양 끝 스위치 번호를 한 줄에 하나씩 출력한다. 최소 비용으로 연결하는 방법이 여러 가지라면 그중 아무 방법이나 출력해도 된다.