漂亮国 有 个村庄，有 条路连接，并且所有的村庄相互可达。
村庄因为自身的交通因素，人口因素，有一个传染力 ，一旦这个村庄爆发疫情，会迅速感染其他距离小于等于 的其他村庄，并且造成连锁反应。
问一开始最少几个受到境外输入，会导致整个漂亮国 个村庄全部被感染。
第一行一个 ，第二行 个 。。
接下来 行，每个三个数 ，表示 到 的有条距离为 的路。
最少几个村庄受到境外输入。
10 1 2 2 2 6 3 4 5 4 3 1 2 5 2 3 1 2 4 5 4 5 2 4 6 4 4 7 3 1 8 1 8 9 5 8 10 4
3
对于 的数据，满足
对于 的数据，满足 ，。
