C 国由 n 座城市与 m 条有向道路组成，城市与道路都从 1 开始编号，经过 i 号道路需要 t_i 的费用。
现在你要从 1 号城市出发去 n 号城市，你可以施展最多 K 次魔法，使得通过下一条道路时，需要的费用变为原来的相反数，即费用从 t_i 变为 -t_i。请你算一算，你至少要花费多少费用才能完成这次旅程。注意：使用魔法只是改变一次的花费，而不改变一条道路自身的 t_i；最终的费用可以为负，并且一个城市可以经过多次（包括 n 号城市）。

【样例1输入】

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

【样例1输出】

 
-8

【样例1解释】

 
依次经过 1 号道路、2 号道路、3 号道路，并在经过 1、2 号道路前使用魔法。

【样例2输入】

 
2 2 2
1 2 10
2 1 1

【样例2输出】

 
-19

【样例2解释】

 
依次经过 1 号道路、2 号道路、1 号道路，并在两次经过 1 号道路前都使用魔法。

【数据范围与提示】

 
对于所有测试点和样例满足：

1 ≤ n ≤ 100，1 ≤ m ≤ 2500，0 ≤ K ≤ 10⁶，1 ≤ u_i,v_i ≤ n，1 ≤ t_i ≤ 10⁹。

数据保证图中无自环，无重边，至少存在一条从 1 号城市到达 n 号城市的路径。

每个测试点的具体限制见下表。