Parity Constraint 최소 스패닝 트리

2019년 연세대학교 최적화 연구실에서 특정 문제에 Parity Constraint(홀짝 제약)를 넣어 푸는 것이 갑자기 유행한 적이 있었다. 졸업한 김강산 선배도 Parity Constraint 관련 논문을 썼다. 이를 기념하여 국렬이는 연세대학교 프로그래밍 경진대회에 Parity Constraint 문제를 내기로 했다.

정점이 $N$개, 비용이 있는 무방향 간선이 $M$개 있는 그래프가 주어진다. 모든 정점에는 1부터 $N$까지 번호가 매겨져 있다. 임의의 정점에서 다른 모든 정점으로 가는 경로는 항상 존재하며, 서로 다른 두 정점 사이에는 최대 한 개의 간선이 있다.

스패닝 트리는 주어진 그래프의 부분 그래프 중 트리인 것을 뜻한다. 스패닝 트리가 가질 수 있는 비용의 합 중 홀수인 최솟값과 짝수인 최솟값을 구하여라.

$N$ $M$ $u_1$ $v_1$ $w_1$ . . . $u_M$ $v_M$ $w_M$

스패닝 트리가 가질 수 있는 비용의 합 중 홀수인 최솟값과 짝수인 최솟값을 출력한다. 해당하는 트리가 존재하지 않으면 -1을 출력한다.

• 2 ≤ N ≤ 100,000.
• 1 ≤ M ≤ 300,000.
• 1 ≤ $u_i$, $v_i$ ≤ N. $u_i$ ≠ $v_i$. $u_i$와 $v_i$는 $i$번째 간선의 양 끝점이다.
• 1 ≤ $w_i$ ≤ 1,000,000,000. $w_i$는 $i$번째 간선의 비용이다.
• 입력으로 주어지는 수는 모두 정수이다.