【问题描述】
众所周知，小y喜欢旅游。
这次，他到了A星球。A星球上有n个城市，城市之间存在有向边。经过每条边有一个时间ti。小y想从1号城市走到n号城市。他想知道从1号城市到n号城市的最少花费时间。
小y又跟A球星的霸主py了一下。他现在有一种魔法，每次可以把一条边的时间取反（相当于时间穿梭）。但这种魔法最多只能使用K次。并且小y经过使用魔法的边后魔法就会消失，但可以再次对这条边使用魔法。现在他又想知道从1号城市到n号城市的最少花费时间是多少(可以为负)。

【输入格式】
输入的第一行为n, m, K，分别表示城市个数、有向边条数还有使用魔法次数。
接下来m行，每行三个整数x, y, z，分别表示有向边(x, y)，经过时间z。

【输出格式】
一行整数表示最短路。

输入样例

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

输出样例

-8

Limitation

1s, 256MiB for each test case.
【数据范围与约定】
30%: n <= 5, m <= 20, K <= 3
60%: n <= 20, m <= 200, K <= 100
100%: n <= 50, m <= 2500, K <= 10^9, z > 0