問題 F : 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_0 b_0 c_0
...
a_{M-1} b_{M-1} c_{M-1}

出力形式

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

制約

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

入出力例

入力例 1

6 5 4
2 1 1
2 5 2
5 1 1
4 3 2
3 6 -1

出力例 1

4

入力例 2

3 1 3
1 2 -10

出力例 2

-10

入力例 2

6 3 5
1 2 0
2 3 10
3 4 0

出力例 2

Impossible

---