问题描述

小ZH今天来到了新的城市，在这个城市中有n个建筑，把建筑链接起来共有m条路径，并且路径中可能存在重边和自环， ​边权可能为负数​。

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

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

输入输出格式

输入格式

第一行包含三个整数 n,m,k

接下来 m行，每行包含三个整数 x,y,z表示存在一条从建筑x到建筑y的有向边，边长为 z。

点的编号为 1∼n。

输出格式

输出一个整数，表示从 1号建筑到 n号建筑的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围

数据范围

任意边长的绝对值不超过 10000。

测试样例

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

3