Description

给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1号点到 n号点的最多经过 k条边的最短距离，如果无法从 1号点走到 n号点，输出 impossible。
注意：图中可能 存在负权回路 。

Input Format

第一行包含三个整数 n,m,k。
接下来 m行，每行包含三个整数 x,y,z，表示存在一条从点 x到点 y的有向边，边长为 z。
点的编号为 1∼n。

Output Format

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

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

3

Hint

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

Source

2.3搜索与图论 bellman-ford