13008번 - 특수 능력

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

성원이는 현재 1번 정점 위에 있다. 성원이는 간선을 이용해서 다른 정점으로 이동할 수 있다. 어떤 간선을 이동할 때 필요한 비용은 간선의 가중치이다. 성원이는 N번 정점까지 이동하는 비용을 최소로 하려고 한다.

성원이는 특수 능력을 가지고 있다. 어떤 간선을 이용할 때, 이 특수 능력을 사용하면 간선의 가중치를 음수(-1을 곱한 값)로 바꿔버릴 수 있게 된다. 하지만, 이 특수 능력은 최대 C번 사용할 수 있다.

특수 능력을 사용해서 간선의 가중치를 음수로 바꾼 후, 그 간선을 사용하면 다시 원래 가중치로 바뀌게 된다. 각 간선은 여러 번 사용할 수도 있으며, 특수 능력을 사용할 수 있는 횟수가 남은 상태로 N번 정점에 도착해도 된다.

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

첫째 줄에 정점의 개수 N, 간선의 개수 M, 특수 능력을 사용할 수 있는 횟수 C가 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 2500, 0 ≤ C ≤ 1,000)

둘째 줄부터 M개의 줄에 간선의 정보 from, to, cost가 주어진다. (1 ≤ from, to ≤ N, 0 ≤ cost ≤ 100,000) from은 간선의 시작점, to는 간선의 도착점이다.

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

첫째 줄에 성원이가 N번 도시로 이동하는 최소 비용을 출력한다.