Description

众所周知，小y喜欢旅游。

这次，他到了A星球。A星球上有 $n$ 个城市，城市之间存在有向边。经过每条边有一个时间 $t_i$。小y想从 $1$ 号城市走到 $n$ 号城市。他想知道从 $1$ 号城市到 $n$ 号城市的最少花费时间。

小y又跟A球星的霸主py了一下。他现在有一种魔法，每次可以把一条边的时间取反（相当于时间穿梭）。但这种魔法最多只能使用 $K$ 次。并且小y经过使用魔法的边后魔法就会消失，但可以再次对这条边使用魔法。现在他又想知道从 $1$ 号城市到 $n$ 号城市的最少花费时间是多少(可以为负)。

Input Format

输入的第一行为 $n, m, K$ ，分别表示城市个数、有向边条数还有使用魔法次数。

接下来 $m$ 行，每行三个整数 $x, y, z$，分别表示有向边 $(x, y)$ ，经过时间 $z$。

Output Format

一行整数表示最短路。

Sample

样例输入1

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

样例输出1

-8

Hint

对于 30%的数据: $n \le 5, m \le 20, K \le 3$

对于 60%的数据: $n \le 20, m \le 200, K \le 100$

对于100%的数据: $n \le 50, m \le 2500, K \le 10^9, z > 0$