Informatica Online Judge

  오작교 [2129 / 0851]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 1   Total Tried : 4


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

하라는 과제는 안 하고 맨날 놀기만 하던 연인 목동 진영이와 직녀 태영이는 화가 나신 옥황상제의 명령으로 인해 멀리 떨어진 두 별에 갇히게 되었다.

이를 불쌍히 여긴 우주 까마귀들이 다리를 만들어 두 사람이 만날 수 있도록 해 주려 한다.
단, 까마귀는 밟히는 방향에 민감해서 이 다리는 단방향이라고 한다.

까마귀들의 정성을 갸륵하게 여긴 옥황상제는 자신이 기르던 백조를 내려보내 그들을 돕도록 하였다.

겨우 진영이와 태영이 따위의 만남을 위해 희생되는 불쌍한 까마귀들을 위해 가장 적은 마릿수가 필요한 경로를 알아내주자.

진영이는 1번 별에 있고 태영이는 N번 별에 있다고 한다.

별에서 별 까지 갈 수 있는 경로와 그 경로를 만드는 데 필요한 까미귀의 마릿수를 알고 있다고 할 때, 진영이와 태영이가 만나기 위해 필요한 까마귀의 마릿수를 구하자.

단, 백조는 신묘한 능력이 있어 한 마리가 한 경로를 이룰 수 있다. 물론 이것도 단방향 다리다.

Input

첫째 줄에 별의 개수 N과 별과 별 사이에 만들 수 있는 경로의 개수 M, 상제가 내려준 백조의 마릿수 K가 공백을 사이에 두고 주어진다.

둘째 줄부터 M개의 줄에 각 경로의 시작별과 끝별, 만드는데 필요한 까마귀의 마릿수가 공백을 두고 입력된다.

0 < N < 100
0 < M < 400
0 < K <= N
0 < 경로 1개에 필요한 마릿수 < 100

Output

동준이와 태영이가 만나기 위해 필요한 까마귀의 최소 마릿수를 출력한다.
만날 수 없을 경우 -1을 출력하라.

IO Example

입력
4 3 1
1 2 2
2 3 5
3 4 7

출력
7

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]