一个神秘生物和人类互相帮助生活的世界。 在这个世界上,有很多锦标赛,你捕获的怪物会相互竞争。 许多男孩和女孩的目标是成为世界上最好的教练。
在锦标赛中,你用捕获的怪物创建一个队伍,并且队伍之间互相战斗。 怪物对之间是有兼容性的,有兼容性很差的情况,也有兼容性一般的情况。 如果兼容性很差,你就不能让这对怪物在同一队伍中。 如果兼容性正常的话 兼容性由数值友情度表示。 在战斗中,全队的友好度总和是胜利的关键。
现在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如果无法创建一支由一只怪物组成的队伍,请在一行上打印“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 中最多出现两次。
- 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
入力例 3
6 3 5 1 2 0 2 3 10 3 4 0
出力例 3
Impossible