对于 John 来说，这是一个非常令人兴奋的星期。作为一名中学老师，他被要求用整个星期的时间向班上的 $n$ 名学生讲授全球变暖的原因和影响。由于 John 对地球充满热情，他打算投入额外的时间和精力，让这个星期对学生们来说既难忘又有意义。为此，他想让学生们准备关于全球变暖的演讲作为家庭作业。为了让这件事对他们来说更容易、更有趣，他要求学生们两人一组进行准备。

当然，将学生分组会带来一个常见的问题，即只有朋友才愿意一起工作。幸运的是，他班上的学生都很友好。特别地，如果 $p$、$q$ 和 $r$ 是三个不同的学生，$p$ 和 $q$ 是朋友，$q$ 和 $r$ 也是朋友，那么 $p$ 和 $r$ 也是朋友。但 John 现在意识到，让学生在家分组工作具有讽刺意味，因为学生可能需要长途跋涉去见他们的组员，这可能会根据交通方式排放二氧化碳等温室气体。本着本周主题的精神，John 要求班上所有的学生计算一下，如果他们要与各自的朋友见面，会排放多少二氧化碳。

利用这些信息，你能否帮助 John 计算出如果他以最优方式安排分组，总共排放的二氧化碳量最少是多少？或者确定是否无法将所有学生都安排成两人一组？

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 200, 0 \le m \le 250$)，分别表示 John 班上的学生人数和班上朋友对的总数。由于 John 不擅长记名字，他给每位学生分配了一个 $1$ 到 $n$ 之间的不同整数标识符。

接下来的 $m$ 行，每行包含三个整数 $p$、$q$ 和 $c$ ($1 \le p, q \le n, 0 \le c \le 10^6$)，表示两个互为朋友的不同学生的标识符，以及如果他们分在一组并因此需要见面时会排放的二氧化碳克数。输入中每对朋友恰好列出一次。

输出格式

输出如果 John 将所有学生以最优方式安排成两人一组时，总共排放的二氧化碳克数；如果无法以这种方式安排学生，则输出 “impossible”。

样例

样例输入 1

5 4
3 1 375
2 5 283
1 4 716
3 4 98

样例输出 1

impossible

样例输入 2

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

样例输出 2

900