시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 81 23 11 24.444%

문제

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

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

3 6 1
1 2 1
1 3 5
2 1 1
2 3 10
3 1 1
3 2 1

예제 출력 1

-9

예제 입력 2

1 1 1000
1 1 100

예제 출력 2

-100000

예제 입력 3

2 3 2
1 2 6
1 2 1
2 1 4

예제 출력 3

-9

예제 입력 4

2 1 100
1 2 1000

예제 출력 4

-1000

출처