Special Ability

There is a directed graph with $N$ vertices and $M$ edges. The vertices are numbered 1 to $N$, and every edge has a weight. Two vertices can be joined by more than one edge, and an edge can start and end at the same vertex.

Seongwon starts on vertex 1. Every time he crosses an edge he pays the weight of that edge. He may cross the same edge as many times as he wants.

Seongwon has a special ability. At the moment he crosses an edge he may use the ability, and then that crossing costs the weight multiplied by $-1$. The edge returns to its original weight right after the crossing, so crossing it again without the ability costs the original weight. He may use the ability at most $C$ times over the whole walk.

Write a program that finds the smallest total cost of a walk that starts at vertex 1 and finishes at vertex $N$. The walk may pass through vertex $N$ earlier and come back to it later, and it may finish at vertex $N$ with unused uses of the ability left.

The first line contains the number of vertices $N$, the number of edges $M$, and the largest number of times the special ability can be used, $C$. ($1 \le N \le 50$, $1 \le M \le 2500$, $0 \le C \le 1000$)

Each of the next $M$ lines describes one edge with the start vertex $u$, the end vertex $v$, and the weight $w$, separated by spaces. The edge can only be crossed in the direction from $u$ to $v$. ($1 \le u, v \le N$, $0 \le w \le 100000$)

Vertex $N$ is always reachable from vertex 1 in the given graph.

Print the minimum cost of moving from vertex 1 to vertex $N$ on the first line.