Global Warming

John teaches middle school, and he spends this whole week teaching his $n$ students about the causes and effects of global warming. For homework he asks them to prepare presentations on global warming, and to make the work lighter he lets them prepare it in groups of two.

Arranging the groups comes with one restriction: only students who are friends are willing to work together. Luckily the friendships in this class satisfy the following property. For three distinct students $p$, $q$ and $r$, if $p$ and $q$ are friends and $q$ and $r$ are friends, then $p$ and $r$ are friends as well.

The students work at home, so a student has to travel to meet a partner, and the trip emits carbon dioxide depending on the mode of transportation. John asked every student to find out how much carbon dioxide a meeting with each of their friends would emit.

Find the smallest total amount of carbon dioxide emitted when all students are split into groups of two friends, or report that no such arrangement exists.

The first line contains the number of students $n$ and the number of friend pairs $m$ ($1 \le n \le 200$, $0 \le m \le 250$). Students are identified by distinct numbers from $1$ to $n$.

Each of the next $m$ lines contains three integers $p$, $q$ and $c$ ($1 \le p, q \le n$, $p \ne q$, $0 \le c \le 10^6$). Here $p$ and $q$ are the numbers of two distinct students who are friends, and $c$ is how many grams of carbon dioxide are emitted when those two are in a group together and have to meet. Every pair of friends is listed exactly once.

Print the total amount of carbon dioxide, in grams, emitted by an optimal arrangement of all students into groups of two friends. If no such arrangement exists, print impossible.