说明

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。

输入格式

• 第一行包含三个整数 n，m，k。
• 接下来 m 行，每行包含三个整数 x，y，z，表示点 x 和点 y 之间存在一条有向边，边长为 z。

输出格式

• 输出一个整数，表示从1号点到n号点的最多经过 k 条边的最短距离。
• 如果不存在满足条件的路径，则输出“impossible”。

样例

3 3 1
1 2 1
2 3 1
1 3 3

3

提示

• 1≤n,k≤500,
  1≤m≤10000,
  任意边长的绝对值不超过10000。