특수 능력 2

$N$개의 정점과 $M$개의 간선으로 이루어진 방향 그래프가 있다. 정점에는 1번부터 $N$번까지 번호가 붙어 있고, 각 간선에는 0 이상의 정수 가중치가 있다. 두 정점 사이에 간선이 여러 개 있을 수도 있고, 시작점과 도착점이 같은 간선이 있을 수도 있다.

성원이는 지금 1번 정점에 있다. 간선을 따라 다른 정점으로 이동하며, 간선 하나를 지나는 비용은 그 간선의 가중치다.

성원이에게는 특수 능력이 있다. 간선을 지날 때 이 능력을 쓰면 그 간선의 가중치에 -1을 곱한 값이 그 번의 비용이 된다. 능력은 최대 $C$번 쓸 수 있고, 한 번 쓸 때 간선 하나를 지나는 데만 적용된다. 같은 간선을 여러 번 지나도 되고, 지날 때마다 능력을 다시 쓸 수 있다. 능력을 쓸 횟수가 남은 채로 $N$번 정점에 도착해도 된다.

성원이가 1번 정점에서 출발해 $N$번 정점에 도착하는 최소 비용을 구하는 프로그램을 작성하시오.

첫째 줄에 정점의 개수 $N$, 간선의 개수 $M$, 특수 능력을 쓸 수 있는 횟수 $C$가 주어진다. ($1 \le N \le 50$, $1 \le M \le 2500$, $0 \le C \le 10^9$)

둘째 줄부터 $M$개의 줄에 간선 하나의 정보 $\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}$은 간선의 시작점, $\text{to}$는 간선의 도착점이고, 이 간선은 $\text{from}$에서 $\text{to}$ 방향으로만 지날 수 있다.

1번 정점에서 $N$번 정점으로 갈 수 있는 그래프만 입력으로 주어진다.

첫째 줄에 성원이가 1번 정점에서 $N$번 정점까지 이동하는 최소 비용을 출력한다.