Special Ability 2

You are given a directed graph with $N$ vertices and $M$ edges. The vertices are numbered from 1 to $N$, and every edge carries an integer weight of 0 or more. Two vertices can be joined by several edges, and an edge may start and end at the same vertex.

Seongwon is standing on vertex 1. He moves to other vertices along edges, and traversing one edge costs that edge's weight.

Seongwon has a special ability. When he traverses an edge, using the ability makes that traversal cost the edge's weight multiplied by -1. He can use the ability at most $C$ times, and one use applies to a single traversal of a single edge. He may traverse the same edge several times, and he may use the ability again on each traversal. He may also arrive at vertex $N$ with uses of the ability left over.

Write a program that finds the minimum cost for Seongwon to start at vertex 1 and arrive at vertex $N$.

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

Each of the next $M$ lines contains one edge as $\text{from}$, $\text{to}$, $\text{cost}$. ($1 \le \text{from} \le N$, $1 \le \text{to} \le N$, $0 \le \text{cost} \le 100000$) $\text{from}$ is the start of the edge and $\text{to}$ is its end, so the edge can be traversed only in the direction from $\text{from}$ to $\text{to}$.

Every graph given as input allows travel from vertex 1 to vertex $N$.

Print the minimum cost for Seongwon to travel from vertex 1 to vertex $N$ on the first line.