허브 명령 전달 출력

문제

스마트 홈에는 N개의 기기가 있고, 1번 기기가 허브이다. 기기 사이에는 M개의 무선 링크가 있다. 각 링크는 양방향이며 전달 지연 d(ms)와 필요 송신 출력 p를 가진다. 양 끝이 같은 링크나 같은 두 기기 사이의 여러 링크도 있을 수 있다. 허브가 N번 기기로 명령을 보내면 명령은 링크를 따라 전달되고, 도착까지 걸리는 시간은 거친 링크들의 지연을 모두 더한 값이다. 집 전체는 송신 출력 상한 P를 하나 정해 공통으로 쓴다. 출력 상한이 P이면 필요 송신 출력이 P 이하인 링크만 사용할 수 있다. 명령은 T ms 이내에 N번 기기에 도착해야 하며, 정확히 T ms 에 도착하는 것도 허용된다. 가능한 경로가 여러 개이면 걸리는 시간이 가장 짧은 경로를 쓴다고 본다. 이 조건을 만족하는 가장 작은 정수 P (P ≥ 0)를 구하시오. N = 1 이면 링크를 쓰지 않아도 도착한 것이므로 답은 0이다. 출력 상한을 아무리 높여도 T ms 이내에 도착할 수 없으면 -1을 출력한다.

입력

첫 줄에 N, M, T 가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 10000, 0 ≤ M ≤ 12000, 0 ≤ T ≤ 10^9 이다. 이어서 M개의 줄에 링크의 양 끝 기기 번호 u, v (1 ≤ u, v ≤ N), 지연 d (1 ≤ d ≤ 10^4), 필요 송신 출력 p (1 ≤ p ≤ 10^6)가 주어진다. 모든 값은 정수이다.

출력

조건을 만족하는 가장 작은 정수 P 를 한 줄에 출력한다. 불가능하면 -1을 출력한다.

4 5 10
1 2 3 5
2 4 4 5
1 3 2 2
3 4 9 3
1 4 20 1

5

1 0 0

0

3 1 100
1 2 5 7

-1

출처: Devin.KR 자체 제작