#316 mst

Loading problem...

Preparing the statement, recent submissions, and submit form.

#316 mst | DOJ

Statement

정점이 $1$ 번부터 $N$ 번까지 번호가 붙은 무향 가중 그래프가 주어진다. 그래프의 최소 스패닝 트리의 가중치 합을 출력하여라.

스패닝 트리가 존재하지 않으면 IMPOSSIBLE을 출력한다. 중복 간선과 자기 간선이 허용된다.

입력은 다음과 같은 형식으로 주어진다.

$N\ M$ $u_1\ v_1\ w_1$ $u_2\ v_2\ w_2$ $\vdots$ $u_M\ v_M\ w_M$

최소 스패닝 트리의 가중치 합을 출력한다. 존재하지 않으면 IMPOSSIBLE을 출력한다.

#	Score	Constraints
1	20	$N \leq 200$ , $M \leq 500$
2	80	추가적인 제약조건이 없다.

Sample 1

Input

Output

https://doj.kr/ko/board/cmspx62m84kwvorfy4pgqot9p jtw7913님의 도움을 받아 제작되었습니다.

Sample 2

Input

Output

IMPOSSIBLE

Sample 3

Input

Output