최소 비용 배수망

워터무 시에는 $1$번부터 $N$번까지 번호가 붙은 건물이 있고, 건물 두 개를 잇는 배수관이 $M$개 있다. 도시 계획이 어긋난 탓에 하수 처리장은 $1$번 건물 하나뿐이다.

각 배수관은 가동 상태이거나 정지 상태다. 가동 중인 배수관만 써서 $1$번 건물이 나머지 모든 건물과 직접 또는 간접으로 이어지면, 가동 중인 배수관의 집합을 올바른 배치라고 한다. 배수관은 건물 두 개를 직접 잇는다. 건물 $X$가 건물 $Y$와 직접 또는 간접으로 이어져 있고 건물 $Y$가 건물 $Z$와 직접 또는 간접으로 이어져 있으면, $X$와 $Z$는 간접으로 이어져 있다.

시청은 지금 배수관 $N - 1$개로 이루어진 올바른 배치를 운영하고 있는데, 유지비가 너무 비싸다고 본다. 배수관마다 가동 중일 때 시가 내야 하는 월 유지비가 있고, 배치의 총비용은 가동 중인 배수관의 유지비 합이다. 정지 상태인 배수관에는 비용이 들지 않는다.

워터무 대학 연구진은 배수관 하나에 쓸 수 있는 실험용 성능 개선 장치를 만들었다. 원하는 배수관 하나를 골라 이 장치를 쓰면 그 배수관의 비용이 $C$에서 $\max(0, C - D)$로 줄어든다. $D$는 장치의 세기다.

시는 배치의 비용을 최소로 만들되 그 작업을 빨리 끝내기를 원한다. 하루에 배수관 하나를 가동하고 다른 배수관 하나를 정지할 수 있다. 가동 중인 배수관의 집합이 올바른 배치가 되고, 그 비용이 모든 올바른 배치와 장치를 쓸 배수관의 모든 선택을 통틀어 최소가 되게 하려면 며칠이 필요한가?

작업 도중에 배치가 올바르지 않아도 되지만, 마지막에는 올바른 배치여야 한다.

첫째 줄에 정수 $N$, $M$, $D$가 주어진다. ($1 \le N \le 100000$, $N - 1 \le M \le 200000$, $0 \le D \le 10^9$)

다음 $M$개 줄에는 정수 $A_i$, $B_i$, $C_i$가 주어진다. 건물 $A_i$와 건물 $B_i$를 잇는 배수관이 있고, 가동 중일 때 월 유지비가 $C_i$라는 뜻이다. ($1 \le A_i, B_i \le N$, $1 \le C_i \le 10^9$)

이 $M$개 줄 중 처음 $N - 1$개가 시가 지금 운영 중인 올바른 배치다.

건물 두 개를 잇는 배수관은 많아야 하나이고, 자기 자신을 잇는 배수관은 없다.

작업을 끝내는 데 필요한 최소 일수를 한 줄에 출력한다. 지금 운영 중인 배치가 이미 최적이면 $0$을 출력한다.

첫 번째 예제에서는 $D = 0$이라 장치를 어느 배수관에 쓰든 유지비가 바뀌지 않는다. 첫날에 건물 $2$와 건물 $3$을 잇는 배수관을 정지하고 건물 $4$와 건물 $1$을 잇는 배수관을 가동하면 된다.

두 번째 예제를 최소 일수로 끝내는 방법 하나는 이렇다. 먼저 건물 $1$과 건물 $2$를 잇는 배수관에 장치를 써서 비용을 $3$으로 줄인다. 첫날에는 건물 $2$와 건물 $3$을 잇는 배수관을 건물 $1$과 건물 $3$을 잇는 배수관으로 바꾸고, 둘째 날에는 건물 $1$과 건물 $4$를 잇는 배수관을 건물 $1$과 건물 $5$를 잇는 배수관으로 바꾼다. 이때 최적 배치의 비용은 $10$이다. 한편 건물 $1$과 건물 $3$을 잇는 배수관이나 건물 $1$과 건물 $5$를 잇는 배수관에는 장치를 쓸 수 없다. 그 배수관의 유지비가 $0$이 되면 최적 배치의 비용이 $11$인데, 비용 $10$을 이미 만들 수 있기 때문이다.

세 번째 예제에서는 지금 운영 중인 배치가 이미 최적이다. 구현할 때 정수 오버플로를 조심해야 한다.