题解

问题描述

给定建筑数 N，道路数 M，距离阈值 K，以及每条道路的连接信息，计算园区内有多少个独立的建筑群。

题目内容

某公司基地园区很大，里面有$N$个建筑，依次编号为$1$到$N$，通过$M$条路将这些建筑连接在一起，这$N$个建筑根据之间的距离，被分为不同的建筑群。云小核喜欢饭后散步，并用步数计算了每条路的长度。经过一段时间的散步，云小核发现了一个规律，两个建筑群间最近的两个建筑之间，步数大于$K$步。两个建筑群之间，可能没有路。云小核把每条路的步数给了你，请你计算园区里有多少个建筑群?

输入描述

第一行有三个整数$N、M、K$，分别表示$N$个建筑，$M$条路，两个建筑群间最近两个建筑之间的最小距离$K$，$2 <= N <= 100$， $1 <= M <= N*(N-1)/2$,$1 <=K<=100000$ 后面有$M$行，每行包含三个整数$a、b、d$，表示建筑$a$和$b$之间的步数为$d$，$1 <= a$,$b <=N$,$1<=d <= 100000$

输出描述

仅有一个整数，表示园区里有多少个建筑群

样例1

输入

6 5 3
1 2 1
1 3 4
2 4 2 
3 5 3
3 6 2

输出

2 

说明

样例2

输入

5 5 4
1 2 1
1 3 4
2 4 2
3 5 2
4 5 5

输出

1

说明

样例3

输入

5 3 4
1 2 1
2 4 2
3 5 2

输出

2

说明