#26 「 快递公司 」

统计

P城有n个村庄,村庄之间有m条双向道路,每条道路有限重。

现在你经营一个快递公司,在这些村庄之间送货。

为了遵守道路限重,如果你要运送一些较重的物品,一些道路就不能走。

你发现如果这样的话,有可能就不存在从一些村庄到另一些村庄的路径。

于是你决定在一些村庄建立飞机场。

不过建飞机场很浪费钱,于是你希望建最少的飞机场实现两两村庄间都能实现配送。

现在你需要回答q个询问,每次询问当只需运送重量小于等于w的物品时,至少需要建多少个飞机场?

输入格式

一行三个数字 n,m,q。

接下来m行,每行三个数字x,y,z。表示有一条从x到y的无向边,限重为z。

接下来q行,每行一个数字w。

输出格式

输出共q行,每行一个整数表示答案。

样例数据

input

3 2 3
1 2 1
2 3 2
1
2
3

output

0
2
3

样例解释

配送重量为1的物品,不需要修建飞机场。

配送重量为2的物品,需要在村庄1修建一个飞机场,再修建一个飞机场在村庄2或村庄3。

配送重量为3的物品,需要在每个城市都修建一个飞机场。

数据规模与约定

$1 \le n,m,q \le 10^5, 1 \le x,y \le n, 0 \le z,w \le 10^9 $。

时间限制:1s

空间限制:512MB

Author: zrt