Social Monsters

There is a world where strange creatures and humans help each other and live together. In this world, tournaments where people pit the monsters they have caught against each other are held often, and many boys and girls aim to become the world's best trainer.

In a tournament, you build a party from the monsters you have caught and battle other parties. A pair of monsters has an affinity, which is either very bad or normal. If the affinity is very bad, the two monsters of that pair cannot be put in the same party. If the affinity is normal, the strength of the affinity is expressed by a number called friendship. In a battle, the sum of the friendship over the whole party decides the outcome.

Now you want to build a party of $K$ monsters out of $N$ monsters. The affinities of $M$ pairs of monsters $(a\_i, \, b\_i)$ are known, each given as an integer $c\_i$. If $c\_i = 0$, the $a\_i$-th monster and the $b\_i$-th monster have a very bad affinity. If $c\_i \, \neq \, 0$, the $a\_i$-th monster and the $b\_i$-th monster have a normal affinity, and their friendship is $c\_i$. For any pair other than the given $M$ pairs, the affinity is normal and the friendship is $0$.

Think about how to choose the party so that the sum of friendship is as large as possible.

The input is given in the following format.

$N$ $M$ $K$

$a\_1$ $b\_1$ $c\_1$

$...$

$a\_M$ $b\_M$ $c\_M$

If a party of $K$ monsters cannot be built, output "Impossible" on one line.

If a party can be built, output the maximum sum of friendship.

• $1 ≤ K ≤ N ≤ 2000$
• $0 ≤ M ≤ N$
• $1 \, ≤ \, a\_i \, \neq \, b\_i \, ≤ N$
• $|c\_i| \, ≤ 10000$
• Each monster appears at most twice in $a\_1, a\_2, …, a\_M, b\_1, b\_2, …, b\_M$.
• $i \, \neq \, j \; ⇒ \; \{a\_i, b\_i\} \, \neq \, \{a\_j, \, b\_j\}$