Can You Send Me 30K?

끊어야 할 땐 결연히!

— 진천우, 「명일방주: 엔드필드」

펠리카의 3만 달러 부탁을 들어주지 못할 위기에 처한 천우는 여러 임무들을 수행해 돈을 벌기로 결심했다. 천우는 4번 협곡의 전선을 연결하는 임무를 맡았다.

4번 협곡은 $N$개의 지역과 서로 다른 두 지역 사이를 잇는 $M$개의 양방향 도로로 이루어져 있다. 각 지역에는 $1$ 이상 $N$ 이하의 서로 다른 번호가 매겨져 있으며, $i$번째 도로는 $u_i$번 지역과 $v_i$번 지역을 연결하는 길이가 $w_i$인 도로이다. 서로 다른 두 지역 사이에 2개 이상의 도로가 있을 수 있다.

전선을 연결하는 시작점인 프로토콜 코어는 $1$번 지역에 위치해 있고, 전력을 공급해야 하는 전력 단말기는 $N$번 지역에 위치해 있다. 천우는 도로를 따라서 $1$번 지역에서부터 $N$번 지역까지 전선을 이으려고 한다.

하지만 전선의 길이는 최대 $P$로 제한되어 있어, 프로토콜 코어에서 전력 단말기까지 한번에 연결하지 못할 수도 있다. 이를 해결하기 위해 4번 협곡의 지역 혹은 도로에 중계기들을 설치할 수 있다. 설치한 중계기에서 길이가 최대 $P$인 전선을 원하는 만큼 뽑아낼 수 있으며, 거리가 $P$ 이하인 다른 설비(중계기, 프로토콜 코어, 전력 단말기)가 있다면 그 설비에 연결할 수 있다. 두 설비 사이의 거리는 어느 한 설비에서 시작해 도로를 따라 다른 한 설비로 이동하는 최단 경로의 길이로 정의된다.

또한 일부 도로는 랜드브레이커들이 점령하고 있어 중계기를 설치한다면 금방 망가지고 말 것이다. 따라서 랜드브레이커들이 점령한 도로 위에는 전선이 지나갈 수는 있지만 중계기를 설치할 수는 없다. 엄밀하게는, $a_i = 1$이면 $i$번째 도로에 중계기를 설치할 수 있으며 $a_i = 0$이면 설치할 수 없다. 지역 위에는 항상 중계기를 설치할 수 있으며, 지역이나 중계기의 크기는 전선의 길이에 영향을 주지 않는다.

중계기는 통합 공업 시스템에서 가장 비용이 많이 드는 설비이기 때문에, 중계기를 최대한 적게 설치하여 전력 단말기에 전력을 공급하려고 한다. 천우를 도와 설치해야 하는 중계기의 최소 개수를 구해주자.

첫 번째 줄에 지역의 수를 나타내는 정수 $N$, 도로의 수를 나타내는 정수 $M$, 전선의 최대 길이를 나타내는 정수 $P$가 주어진다. $(2 \le N \le 200 \, 000;\; 1 \le M \le 200 \, 000;\; 1 \le P \le 10^9)$

두 번째 줄부터 다음 $M$개의 줄 중 $i$번째 줄에는 $i$번째 도로가 잇는 두 지역의 번호 $u_i$와 $v_i$, 도로의 길이 $w_i$, 중계기 설치 가능 여부 $a_i$가 공백을 사이에 두고 주어진다. $(1 \le u_i, v_i \le N;\; u_i \neq v_i;\; 1 \le w_i \le 10^9;\; a_i \in \{0,1\})$

첫 번째 줄에 전력 단말기에 전력을 공급하기 위해 설치하는 중계기의 최소 개수를 출력한다.

만약 어떻게 중계기를 설치해도 전력 단말기에 전력을 공급할 수 없다면, 대신 But I dont have 30k을 출력한다.