Statement
끊어야 할 땐 결연히!
— 진천우, 「명일방주: 엔드필드」
펠리카의 3만 달러 부탁을 들어주지 못할 위기에 처한 천우는 여러 임무들을 수행해 돈을 벌기로 결심했다. 천우는 4번 협곡의 전선을 연결하는 임무를 맡았다.
4번 협곡은 개의 지역과 서로 다른 두 지역 사이를 잇는 개의 양방향 도로로 이루어져 있다. 각 지역에는 이상 이하의 서로 다른 번호가 매겨져 있으며, 번째 도로는 번 지역과 번 지역을 연결하는 길이가 인 도로이다. 서로 다른 두 지역 사이에 2개 이상의 도로가 있을 수 있다.
Input
첫 번째 줄에 지역의 수를 나타내는 정수 , 도로의 수를 나타내는 정수 , 전선의 최대 길이를 나타내는 정수 가 주어진다.
Output
첫 번째 줄에 전력 단말기에 전력을 공급하기 위해 설치하는 중계기의 최소 개수를 출력한다.
만약 어떻게 중계기를 설치해도 전력 단말기에 전력을 공급할 수 없다면, 대신 But I dont have 30k을 출력한다.
Samples
예제 1
입력
5 5 3
1 2 1 0
2 3 3 0
3 5 1 1
1 4 2 0
4 5 4 1
출력
1
예제 2
입력
3 2 5
1 2 5 1
2 3 7 0
출력
But I dont have 30k
예제 3
입력
5 6 80
1 2 15 1
1 3 70 0
2 3 45 0
2 4 25 0
3 4 10 1
3 5 25 1
출력
0
예제 4
입력
15 19 80
1 2 90 1
1 4 50 1
1 5 50 1
2 3 50 0
2 4 60 1
2 8 140 0
3 5 60 0
3 6 90 0
3 11 70 1
3 12 160 0
6 7 50 1
6 12 110 0
8 9 80 1
9 10 60 0
9 11 80 0
11 12 120 1
12 13 50 0
12 14 50 0
14 15 80 0
출력
5
다음 그림은 이 예제를 설명한 그림이다. 파란 간선은 인 간선을, 빨간 간선은 인 간선을 의미한다.