4

파이프 개선 장치

시간제한 : 3초

어떤 도시에는 1, 2, ... , n. 번 건물이 있고, m개의 하수도 파이프가 빌딩 사이에 연결되어있다. 하지만, 도시 계획이 잘못 되어 1번 건물에만 하수도 처리 시설이 설치되어있다. 건물들 사이에 연결되어있는 각각의 하수도 파이프를 잠그거나 열 수 있다. 파이프들을 잠그거나 열어 적당한 도시 하수도 처리 계획이 수행될 수 있는데, 1번 건물에 직간접적으로 다른 건물들이 연결되어야 한다. (두 건물 사이의 파이프를 열면 직접 연결되는 것이고, 다른 건물을 거쳐 연결되면 간접적으로 연결되는 것이다.)

그 도시의 지방자치정부는 (n-1)개의 파이프만 열어 도시 하수도 처리 계획을 수행할 수 있도록 만들고 싶어 한다. 하지만, 너무 많은 비용이 들어가는 것이 아닐지 우려하고 있다! 파이프들을 열면 관리비가 매달 들어가게 된다.

경곽 학생들은 R&E 연구를 통해 파이프 효율 개선 장치를 만들었는데, 그렇게 만든 장치를 이용해 1개 파이프의 관리비를 줄일 수 있다. 어떤 파이프의 매달 관리비가 c라고 하고, 효율 개선 장치의 개선 효과를 d라고 하면, 그 효율 개선 장치가 설치된 파이프의 관리비는 max(0, c-d)가 된다.

도시 정부는 도시 하수도 처리 계획을 수행하는데 필요한 비용을 최소화하고, 최대한 빨리 그 계획을 실행하고 싶어 한다. 하루에 1개의 파이프를 열고, 1개의 파이프를 잠글 수 있다.

최소 비용의 하수도 처리 계획을 수행하기 위해 필요한 준비는 며칠 만에 가능할까? 1개의 파이프 효율 장치를 사용할 수 있다.

입력형식

첫 줄에는 건물 개수(n), 파이프 연결 개수(m), 효율 개선 장치 효과(d)가 공백을 두고 입력된다. ([eqn: 1 LEQ n LEQ `100,000], [eqn: n-1 LEQ m LEQ `200,000], [eqn: 0 LEQ d` LEQ `10 ^{9}])

그 다음 m 개의 줄에는 파이프가 연결되는 2개의 건물번호([eqn: A _{i}], [eqn: B _{i}])와 파이프 사용 비용([eqn: C _{i}])이 공백을 두고 입력되고([eqn: 1 LEQ `A _{i} ,`B _{i} LEQ `n], [eqn: 1 LEQ C _{i} LEQ `10 ^{9}]), 이 중 n-1개는 현재 열려 있는 파이프들이다.(두 건물 사이에는 적어도 1개 이상의 파이프가 연결되어있고, 건물 자신으로 다시 연결되는 파이프는 없다.)

출력형식

하수도 처리 계획을 최소비용으로 수행할 수 있도록 조정하는데 필요한 최소 날 수를 출력한다.

입출력 예시

입력1

4 4 0

1 2 1

2 3 2

3 4 1

4 1 1

출력1

1

설명 : 파이프 개선 효과(d)가 없다. 2-3을 닫고 4-1을 열어 하루 만에 최소 관리비 상태로 바꿀 수 있다.

입력2

5 6 2

1 2 5

2 3 5

1 4 5

4 5 5

1 3 1

1 5 1

출력2

2

설명 : 1-2에 장치를 붙여 비용을 3으로 만들고, 첫 날 2-3으로 연결된 파이프를 잠그고 1-3 파이프를 연다. 두 번째 날 1-4 파이프를 잠그고 1-5 파이프를 연다. 전체 관리비용이 10이 되고 최소가 된다. 만약, 1-3 이나 1-5 파이프에 개선 장치를 붙이면 그 파이프의 관리비는 0이 되지만 그렇게 되면 전체 관리비용을 11보다 작게 만들 수 없다.

입력3

4 4 0

1 2 2147483647

2 3 2147483647

3 4 2147483647

4 1 2147483649

출력3

0