22440번 - Social Monsters 다국어

不思議な生き物と人間が互いに助け合って生きている世界． この世界では自分で捕まえたモンスター同士を戦わせる大会が盛んに行われており， 多くの少年少女達が世界一のトレーナーを目指している．

大会では自分が捕まえたモンスターからパーティを作り，パーティ同士のバトルをする． モンスターのペアには相性があり，相性が非常に悪い場合と普通の場合がある． 相性が非常に悪い場合，そのペアのモンスターを同じパーティに入れることはできない． 相性が普通の場合には，友情度という数値で相性の良さが表現される． バトルでは，パーティ全体の友情度の和が勝負の鍵となる．

いま$N$匹のモンスターから$K$匹のモンスターからなるパーティを作りたい． $M$個のモンスターのペア$(a_i,   b_i)$に対して相性が分かっており，整数 $c_i$ で表されている． $c_i = 0$ のとき，$a_i$ 番目のモンスターと $b_i$ 番目のモンスターは相性が非常に悪いことを意味する． $c_i  ≠  0$ のとき，$a_i$ 番目のモンスターと $b_i$ 番目のモンスターは相性が普通であり，その友情度は $c_i$ であることを意味する． 与えられた$M$個のペア以外は，相性が普通であり，それらの友情度はすべて$0$である．

パーティの友情度の和を最大にする選び方を考えてみよう．

入力は以下の形式で与えられる

$N$ $M$ $K$

$a_1$ $b_1$ $c_1$

$...$

$a_M$ $b_M$ $c_M$

$K$匹のモンスターからなるパーティを作ることができない場合は1行に "Impossible" を出力せよ．

パーティを作ることができるとき，友情度の和の最大値を出力せよ．

• $1 ≤ K ≤ N ≤ 2000$
• $0 ≤ M ≤ N $
• $1   ≤   a_i   ≠   b_i   ≤ N$
• $|c_i|   ≤ 10000$
• 各モンスターは $a_1, a_2, …, a_M, b_1, b_2, …, b_M$ の中に高々2回しか現れない．
• $i   ≠   j   ⇒  \{a_i, b_i\}   ≠   \{a_j,   b_j\} $