22990번 - 사이클 스페셜 저지

정점이 $N$개, 가중치가 있는 간선이 $M$개인 방향 그래프가 주어진다.

경로는 두 정점을 잇는 간선의 수열을 의미하고, 사이클은 시작점과 끝점이 같은 경로를 의미한다. 사이클 중에서 단순 사이클은 시작점과 끝점을 제외하고 중복되는 정점이 없는 사이클을 의미한다.

주어진 그래프에서 가중치의 합이 최소가 되도록 모든 정점을 포함하고 정점과 간선이 서로 겹치지 않는 단순 사이클의 집합을 구하는 프로그램을 작성하시오.

다음과 같이 입력이 주어진다.

• $N$은 정점의 개수이고 $M$은 간선의 개수이다. ($2 \le N \le 200$, $0 \le M \le N\left(N-1\right)$)
• $u_i$ $v_i$ $w_i$는 정점 $u_i$에서 $v_i$로 가는 가중치 $w_i$의 간선이 존재한다는 뜻이다. ($1 \le u, v \le N$, $u \ne v$, $-10^9 \le w \le 10^9$)

주어진 그래프 내에서 루프는 존재하지 않으며, 서로 다른 두 정점 사이에 최대 한 개의 간선이 존재한다.

모든 정점을 포함하고 정점과 간선이 서로 겹치지 않는 단순 사이클의 집합이 존재하는 경우 첫 번째 줄에 1을 출력한다. 그렇지 않으면 0을 출력한다.

모든 정점을 포함하고 정점과 간선이 서로 겹치지 않는 단순 사이클의 집합이 존재하는 경우, 두 번째 줄에 이러한 집합들의 가중치의 합의 최솟값을 출력하고, 이후 $N$개의 줄에 걸쳐서 해당 집합의 단순 사이클에 속한 간선들을 출력한다. 간선들의 출력 순서는 상관없으며, 답이 여러 개인 경우 그 중 아무 것이나 출력하면 된다.