26605번 - 형광펜 강민우 스페셜 저지

문제

민우는 명장 남정훈의 광팬이다. 다가오는 정훈이의 졸업을 맞아 깜짝 이벤트를 고민하던 민우는 정훈이의 졸업을 축하하는 현수막을 학교 곳곳에 걸기로 한다.

현수막은 학교 건물과 건물을 잇는 모든 길에 설치할 수 있으며 건물과 건물 사이의 길은 하나뿐이며 양방향으로 통행 가능하다. 또한 각 건물에서 다른 모든 건물로 가는 경로가 존재한다. 이때, 민우가 원하는 조건은 다음과 같다.

1. 정훈이가 강의를 듣고 학회방으로 가는 길에 반드시 한 번 이상은 현수막을 볼 수 있어야 한다.
2. 1번 조건을 만족하는 경우 중 현수막을 설치하는 총비용이 최소가 되어야 한다.
3. 1번과 2번 조건을 만족하면서 가능하다면 민우가 있는 건물에서도 현수막을 볼 수 있어야 한다. 즉, 민우가 있는 건물과 연결된 길에 현수막이 하나 이상 걸려야 한다.

민우를 도와 어떤 길들에 현수막을 설치하면 될지 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 학교 건물 수 $N$과 길의 수 $M$이 주어진다. $(2 \leq N \leq 100; ,円 1 \leq M \leq 100)$

두 번째 줄에 정훈이가 강의를 듣는 건물의 번호 $A$와 학회방이 있는 건물의 번호 $B,ドル 민우가 있는 건물의 번호 $K$가 주어진다. 각 건물의 번호는 1번부터 $N$번까지 매겨져 있다. $(A \neq B)$

세 번째 줄부터 $M$개의 줄에 두 건물의 번호와 그 사이 길에 현수막을 설치하는 비용인 정수 $c$가 주어진다. $(1 \leq c \leq 100 ,円 000)$

출력

첫째 줄에 정훈이가 학회방으로 갈 때 한 번 이상은 현수막을 볼 수 있도록 설치하는 최소 비용을 출력한다.

둘째 줄에 최소 비용으로 현수막을 설치했을 때, 민우의 건물에서 현수막을 볼 수 있는 경우가 없다면 $-1$을 출력한다.

그렇지 않다면 둘째 줄에 현수막을 설치할 길의 개수를 출력하고, 셋째 줄부터 현수막을 설치할 각 길이 잇는 두 건물 번호를 공백으로 구분하여 출력한다.

정답이 여러 가지인 경우에는 아무거나 출력한다.

제한

힌트