지구 온난화

중학교 교사 존은 이번 주 내내 학생 $n$명에게 지구 온난화의 원인과 영향을 가르친다. 과제로는 지구 온난화를 주제로 한 발표를 준비하게 했고, 부담을 덜어 주려고 두 명씩 조를 짜서 준비하게 했다.

조를 짜는 데에는 제약이 하나 있다. 서로 친구인 학생끼리만 같은 조가 된다. 다행히 이 반의 친구 관계는 다음 성질을 만족한다. 서로 다른 학생 $p$, $q$, $r$에 대해 $p$와 $q$가 친구이고 $q$와 $r$이 친구이면 $p$와 $r$도 친구다.

학생들은 과제를 집에서 하므로 조원을 만나러 이동해야 하고, 이동 수단에 따라 이산화탄소가 배출된다. 존은 학생마다 각 친구를 만날 때 배출되는 이산화탄소의 양을 미리 조사해 두었다.

모든 학생을 친구 두 명씩의 조로 빠짐없이 나눌 때, 배출되는 이산화탄소 총량의 최솟값을 구하라. 그렇게 나누는 방법이 없으면 그 사실을 알려야 한다.

첫째 줄에 학생 수 $n$과 친구인 쌍의 개수 $m$이 주어진다 ($1 \le n \le 200$, $0 \le m \le 250$). 학생은 $1$부터 $n$까지의 서로 다른 번호로 구분한다.

다음 $m$개 줄에는 각각 세 정수 $p$, $q$, $c$가 주어진다 ($1 \le p, q \le n$, $p \ne q$, $0 \le c \le 10^6$). $p$와 $q$는 친구인 서로 다른 두 학생의 번호이고, $c$는 두 학생이 같은 조가 되어 만날 때 배출되는 이산화탄소의 양(그램)이다. 친구인 쌍은 입력에 정확히 한 번씩만 나온다.

모든 학생을 친구 두 명씩의 조로 나누는 최적의 방법에서 배출되는 이산화탄소 총량을 그램 단위로 출력한다. 그렇게 나눌 수 없으면 impossible을 출력한다.