소셜 몬스터

이상한 생물과 인간이 서로 돕고 살아가는 세계가 있다. 이 세계에서는 자신이 잡은 몬스터끼리 싸우게 하는 대회가 활발하게 열리고, 많은 소년소녀가 세계 최고의 트레이너를 꿈꾼다.

대회에서는 자신이 잡은 몬스터로 파티를 만들고, 파티끼리 배틀을 한다. 몬스터 쌍에는 궁합이 있어, 궁합이 매우 나쁜 경우와 보통인 경우가 있다. 궁합이 매우 나쁘면 그 쌍의 몬스터를 같은 파티에 넣을 수 없다. 궁합이 보통이면 우정도라는 수치로 궁합의 좋음을 나타낸다. 배틀에서는 파티 전체의 우정도 합이 승부의 관건이 된다.

지금 $N$마리의 몬스터 중 $K$마리로 파티를 만들려고 한다. $M$개의 몬스터 쌍 $(a\_i, \, b\_i)$에 대해 궁합을 알고 있고, 정수 $c\_i$로 나타난다. $c\_i = 0$이면 $a\_i$번째 몬스터와 $b\_i$번째 몬스터의 궁합이 매우 나쁘다는 뜻이다. $c\_i \, \neq \, 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$마리의 몬스터로 파티를 만들 수 없으면 한 줄에 "Impossible"을 출력한다.

파티를 만들 수 있으면 우정도 합의 최댓값을 출력한다.

• $1 ≤ K ≤ N ≤ 2000$
• $0 ≤ M ≤ N$
• $1 \, ≤ \, a\_i \, \neq \, b\_i \, ≤ N$
• $|c\_i| \, ≤ 10000$
• 각 몬스터는 $a\_1, a\_2, …, a\_M, b\_1, b\_2, …, b\_M$ 안에 많아야 2번 나타난다.
• $i \, \neq \, j \; ⇒ \; \{a\_i, b\_i\} \, \neq \, \{a\_j, \, b\_j\}$