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