This is a very exciting week for John. The reason is that,
as a middle school teacher, he has been asked to dedicate the
entire week to teaching his class of $n$ students about the cause and
effect of global warming. As John is very passionate about his
planet, he’s going to spend extra time and effort to make this
week memorable and rewarding for the students. Towards that,
one of the things he wants to ask them to do is to prepare, as
homework, presentations about global warming. To make this a
little easier for them, as well as more fun, he has asked them
to do this in groups of two.
Of course arranging the students into groups comes with the
usual headache, namely that only friends are willing to work
together. Luckily the students in his class are a friendly
bunch. In particular, if $p$, $q$ and $r$ are three distinct students, and
$p$ and $q$ are friends, and $q$ and $r$ are friends, then $p$ and $r$ are also friends. But John now
realizes the irony in asking his students to work at home in
groups, as students may have to travel to meet their group
partner, which may emit greenhouse gases such as carbon
dioxide, depending on their mode of transportation. In the
spirit of this week’s topic, John asked all the students in his
class to calculate, for each of their friends, how much carbon
dioxide would be emitted if they were to meet up with the
respective friend.
Using this information, can you help John figure out what is
the minimum total amount of carbon dioxide that will be emitted
if he arranges the groups optimally, or determine that it’s not
possible to arrange all the students into groups of two
friends?
Input
The first line contains two integers $n$ and $m$ ($1
\leq n \leq 200$, $0 \leq
m \leq 250$), the number of students in John’s class,
and the total number of pairs of friends in the class. As John
is bad with names, he has given each of his students a distinct
integer identifier between $1$ and $n$.
Each of the next $m$
lines contains three integers $p$, $q$ and $c$ ($1
\leq p, q \leq n$, $0 \leq
c \leq 10^6$), the identifiers of two distinct students
that are friends, and how many grams of carbon dioxide would be
emitted if they were in a group together, and thus had to meet.
Each pair of friends is listed exactly once in the input.
Output
Output the minimum total amount of carbon dioxide, in grams,
that would be emitted if John arranges all students optimally
into groups of two friends, or “impossible” if there is no way to arrange the
students into groups in that way.
Sample Input 1 
Sample Output 1 
5 4
3 1 375
2 5 283
1 4 716
3 4 98

impossible

Sample Input 2 
Sample Output 2 
6 7
5 6 600
2 5 200
3 5 400
6 3 500
1 4 300
3 2 400
6 2 200

900
