K번째 최단 경로

방향 가중 그래프에서 정점 s부터 정점 t까지의 K번째 최단 경로 길이를 구한다. 경로는 같은 정점을 여러 번 방문할 수 있다. K번째 최단 경로가 없으면 -1을 출력한다.

각 정점을 최대 K번 방문하는 수정된 다익스트라로 구현한다.

입력

첫째 줄에 정점 수 N, 간선 수 M, K가 주어진다.

둘째 줄에 출발 정점 s와 도착 정점 t가 주어진다.

다음 M개 줄에 간선의 출발 정점, 도착 정점, 가중치가 주어진다.

• 1 ≤ N ≤ 1,000
• 1 ≤ M ≤ 2,000
• 1 ≤ K ≤ 10
• 1 ≤ 가중치 ≤ 1,000

출력

K번째 최단 경로 길이를 출력한다. 없으면 -1을 출력한다.

예제 입력 1

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

예제 출력 1

6