Andy 是南京大学的一名普通学生。一天，他在梦中发现自己穿越到了一个仙境。这个仙境由若干个地点组成，一些双向道路连接着其中的某些地点，每条道路都有不同的通行时间。

被迷人的风景所吸引，Andy 想要游览仙境中的一些地点。他希望选择恰好 $k$ 个不同的地点并依次游览。在游览完最后一个地点后，他必须回到第一个地点，因为那是他梦开始的地方。他所选择的任意两个相邻地点之间（包括最后一个和第一个）都必须有道路直接相连。此外，他希望最大化在这些地点之间移动所花费的总时间，以便更好地欣赏美景。

例如，在第一组样例数据中，你可以选择从地点 1 出发，依次游览地点 3、5、2，最后回到地点 1。总耗时为 21 分钟，这被证明是最优的。

然而，寻找这样的旅行计划对 Andy 来说太难了，所以他想寻求你的帮助。你能帮他找到这样一个最优计划吗？

输入格式

输入的第一行包含三个整数 $n, m, k$ ($2 \le n \le 300, 1 \le m \le 300, 3 \le k \le 10$)，分别表示仙境中的地点数量、道路数量以及 Andy 想要游览的地点数量。地点编号为 $1$ 到 $n$。

接下来的 $m$ 行描述了地点之间的道路。每行包含三个整数 $u, v, t$ ($1 \le u, v \le n, u \neq v, 1 \le t \le 10^8$)，表示地点 $u$ 和 $v$ 之间有一条双向道路，沿该道路双向通行均需花费 $t$ 分钟。保证仙境中任意两个地点之间最多只有一条道路。

输出格式

输出一行，包含一个整数，表示最大总旅行时间。如果无法找到任何有效的旅行计划，则输出 impossible。

样例

输入 1

5 7 4
1 2 2
1 3 3
2 3 4
4 3 1
5 3 7
4 5 6
2 5 9

输出 1

21

输入 2

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

输出 2

impossible