골목 대장 호석 - 기능성

호석이는 소싯적에 골목 대장으로 살았다. 호석이가 살던 마을에는 교차로 N개와 골목 M개가 있다. 교차로 번호는 1번부터 N번까지이다. 골목은 서로 다른 두 교차로를 양방향으로 이으며, 임의의 두 교차로를 잇는 골목은 최대 하나만 존재한다. 분신술을 쓰는 호석이는 모든 골목에 분신을 두었고, 골목마다 통과하는 사람에게 요금을 수금한다. 수금액은 골목마다 다를 수 있다.

당신은 A번 교차로에서 B번 교차로까지 C원을 가지고 가려고 한다. 호석이의 횡포가 짜증 나지만 분신술을 이길 방법이 없어서 돈을 내고 가기로 한다. 다만 이왕 지나갈 거라면 최소한의 수치심을 받고 싶다. 당신이 받는 수치심은 경로에서 가장 많이 낸 돈에 비례하므로, 갈 수 있는 여러 방법 중 최소한의 수치심을 받는 쪽을 택하려 한다. 즉, 한 골목에서 내야 하는 최대 요금을 최소화하는 것이다.

예를 들어 위 그림처럼 교차로 5개와 골목 5개가 있고, 당신이 1번 교차로에서 3번 교차로로 가려 한다고 하자. 10원을 들고 출발하면 두 가지 경로로 갈 수 있다. 1번 -> 2번 -> 3번 교차로로 가면 총 10원이 필요하고 이 과정의 최대 수금액은 5원이며, 1번 -> 4번 -> 5번 -> 3번 교차로로 가면 총 8원이 필요하고 최대 수금액은 6원이다. 수치심이 가장 적은 경로는 최대 수금액이 5인 경로이다. 그러나 8원밖에 없다면 앞의 경로는 갈 수 없으므로 최대 수금액이 6인 경로로 가는 것이 최선이다.

앞선 예제를 통해, 수치심을 줄이고 싶을수록 같거나 더 많은 돈이 필요하고, 수치심을 더 감수하면 같거나 더 적은 돈이 필요하다는 것을 알 수 있다. 마을의 지도와 골목마다 호석이가 수금하는 금액을 안다면, 한 골목에서 내야 하는 최대 요금의 최솟값을 계산하라. 지금 가진 돈으로는 목표 지점에 절대로 갈 수 없다면 -1을 출력하라.

첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C가 공백으로 구분되어 주어진다. 이어서 M개 줄에 걸쳐 각 골목이 잇는 교차로 두 개의 번호와 골목의 수금액이 공백으로 구분되어 주어진다. 같은 교차로를 잇는 골목은 최대 한 번만 주어지며, 골목은 양방향이다.

호석이가 지키고 있는 골목을 통해 시작 교차로에서 도착 교차로까지 C원 이하로 가는 경로들 중에서, 지나는 골목 요금의 최댓값의 최솟값을 출력하라. 갈 수 없다면 -1을 출력한다.

• 1 ≤ N ≤ 10
• 1 ≤ M ≤ N × (N-1) / 2
• 1 ≤ C ≤ 10,000
• 1 ≤ 골목 별 수금액 ≤ 1,000
• 1 ≤ A, B ≤ N, A ≠ B
• 골목이 잇는 교차로의 번호는 서로 다르다.