33958번 - Home Sweet Home

문제

포스텍은 정점 $N$개, 간선 $M$개의 가중치 있는 단순 양방향 연결 그래프 $G$로 표현할 수 있다. 포스텍의 유일한 출구는 1ドル$번 정점에 있다. 범수는 이 출구로 학교를 빠져나가기 위해 포닉스에게 도움을 청했다.

하지만 포닉스는 사실 범수가 포스텍에 최대한 오래 머물렀으면 한다! 하지만 아무 것도 하지 않는다면 눈치 빠른 범수에게 금새 발각될 것이다. 따라서 포닉스는 그래프에 쓸모 없는 간선 하나를 추가해 범수를 속이려 한다.

쓸모 없는 간선 $e$란 다음과 같은 조건을 만족하는 $u$번 정점과 $v$번 정점을 잇고 가중치가 음이 아닌 정수 $w$인 양방향 간선이다.

• 1ドル\le u<v\le N,0\le w\le K$
• $G$에 $u$번 정점과 $v$번 정점을 직접 잇는 간선이 없어야 한다. 즉, 그래프 $G$에 간선 $e$를 추가한 그래프 $G\cup e$ 역시 단순 그래프여야 한다.
• 그래프 $G$에서 $a$번 정점에서 $b$번 정점까지의 최단거리를 $dist_G(a,b)$라 하자. 이때 모든 1ドル\le i\le N$에 대해 다음이 성립해야 한다. \[dist_G(i,1)\le dist_{G\cup e}(i,1)\] 즉, 간선을 추가함으로써 어떤 정점에서 1ドル$번 정점까지의 최단거리가 더 짧아지면 안 된다.

포닉스가 추가할 수 있는 서로 다른 쓸모 없는 간선의 개수를 구하여라.

입력

첫 번째 줄에 각각 정점의 개수, 간선의 개수, 가중치의 최댓값을 의미하는 세 정수 $N,ドル $M,ドル $K$가 공백으로 구분되어 주어진다. $(2\le N\le 300\ 000;1\le M\le 500\ 000;1\le K\le 10^8)$

두 번째 줄부터 $M$개의 줄에 걸쳐 포스텍의 간선을 나타내는 세 정수 $u,v,w$가 공백으로 구분되어 주어진다. 이는 $u$번 정점과 $v$번 정점을 잇는 가중치 $w$의 간선을 의미한다. $(1\le u<v\le N;0\le w\le K)$

출력

포닉스가 추가할 수 있는 서로 다른 쓸모 없는 간선의 개수를 출력한다.

제한

힌트