특수 능력

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

성원이는 1번 정점에서 출발한다. 간선을 한 번 지날 때마다 그 간선의 가중치만큼 비용이 든다. 같은 간선을 여러 번 지나도 된다.

성원이에게는 특수 능력이 있다. 간선을 지나는 순간에 이 능력을 쓰면 그 간선을 지나는 비용이 가중치에 $-1$을 곱한 값이 된다. 능력을 써서 지나간 간선은 곧바로 원래 가중치로 돌아오므로, 같은 간선을 능력 없이 다시 지나면 원래 가중치만큼 비용이 든다. 능력은 이동 전체에서 최대 $C$번까지 쓸 수 있다.

1번 정점에서 출발해 $N$번 정점에서 이동을 마칠 때 드는 비용의 합이 가장 작아지는 값을 구하는 프로그램을 작성하시오. 이동 도중에 $N$번 정점을 지나쳤다가 나중에 다시 돌아와도 되고, 능력을 쓸 수 있는 횟수가 남은 상태로 $N$번 정점에 도착해도 된다.

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

둘째 줄부터 $M$개의 줄에 간선의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 간선의 시작 정점 $u$, 도착 정점 $v$, 가중치 $w$가 공백으로 구분되어 주어진다. 간선은 $u$에서 $v$ 방향으로만 지날 수 있다. ($1 \le u, v \le N$, $0 \le w \le 100000$)

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

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