시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 74 36 27 45.000%

문제

코리아 통신회사에서는 3인통화 서비스를 제공한다. 이 서비스에서는 두 사람이 아니라 세 사람이 통화할 수 있도록 해준다. 전화망은 스위치들을 연결하여 구성되어 있으며, 각 통화자들은 스위치에 연결하여 전화망에 접속한다. 두 스위치들은 양방향으로 신호를 보낼 수 있는 링크에 의하여 연결되어 있다. 모든 스위치들은 전화망에 의하여 연결되어 있어서 스위치에 접속한 사람들은 다른 스위치에 연결한 사람과 항상 통화할 수 있다. 전화망에서 두 개의 스위치를 연결하는 링크를 사용하는 비용은 주어져 있다.

통신회사에서는 이들 세 사람을 전화망을 통하여 연결해주는데, 가장 비용이 적게 되도록 연결하고자한다. 세 사람이 연결한 스위치가 주어졌을 때, 이 스위치들을 비용이 가장 적게 되도록 연결하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 두 개의 정수가 있다. 첫 번째 정수 n(1<=n<=1000) 는 전화망에 있는 스위치의 개수를 나타내며, 두 번째 정수 m은 스위치와 스위치를 연결하는 링크의 개수를 나타낸다. 단, 같은 스위치들을 연결하는 링크는 1 개 이상 존재하지 않는다. 각 스위치들은 1번부터 차례로 n 번 까지 번호가 부여된다. 다음 m개의 줄에는, 각 줄에 세 개의 정수가 주어진다. 처음의 두 개의 정수는 하나의 링크에 의하여 연결되는 두 스위치의 번호를 나타내며, 세 번째 정수는 그 링크를 사용하는 비용을 나타내는 양의 정수이다. 이 정수는 100 보다 작다. 입력의 마지막 줄에는 세 개의 정수가 주어 진다. 이 정수는 세 명의 통화자가 연결되어 있는 스위치 번호이며, 세 정수는 모두 다르다.

출력

첫 줄에는 3자 통화를 하는데 있어서 가장 적은 비용으로 통화할 때 드는 비용을 나타내는 정수 출력한다. 두 번째 줄에는 세명의 통화자를 연결하는 네트워크 상에서의 링크의 수를 출력한다. 그 다음 줄부터 각 줄에는 하나의 링크에 연결되는 두 개의 스위치 번호를 출력한다.  비용이 최소가 되도록 연결하는 방법이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력

8 12
1 2 20
2 3 8
2 4 3
2 5 3
2 6 6
3 5 2
3 6 9
4 7 5
5 6 1
5 7 7
6 8 4
7 8 6
1 4 6

예제 출력

27 4
1 2
2 4
2 5
5 6

힌트

출처

Olympiad > Balkan Olympiad in Informatics > BOI 1998 4번