GDUT国有$n$个城市

Tmk很喜欢去旅游，他通过坐巴士去游玩GDUT国。

一共有$m$条公交线，对于第i条公交线，连接两个城市$a_i,b_i$，表示第$a_i$个城市可以坐公交到第$b_i$个城市，第$b_i$个城市也能坐公交到第$a_i$个城市，但必须要等$m_i$分钟才能上车。

Tmk不喜欢等公交太长时间，如果他等一部公交等了超过$t$分钟，他会发烂砸。

问有多少对城市$(x,y)$，使得tmk从第x个城市出发到达第$y$个城市而不发烂砸。

注意$(x,y)$和$(y,x)$属于两种方案

注意$(x,x)$不属于一种方案

输入格式

第一行包含三个整数,$n$,$m$,$q$，分别表示城市数，公交线数和询问数

接下来的m行每行有三个整数，分别表示$a_i,b_i,m_i$

接下来$q$行，每行一个整数$t$，表示询问

输出格式

对于每个询问，每行输出一个整数，表示答案

样例

样例输入

5 5 3
2 3 6334
1 5 15724
3 5 5705
4 3 12382
1 3 21726
6000
10000
13000

样例输出

2
6
12

来源

noip2016提高模拟3

数据范围与提示

• $20$的数据$n \leq 20,m \leq 400,q \leq 50$
• $20$的数据 $q=1$
• $100$的数据  $n \leq 20000,m \leq 100000,q \leq 5000$
• $1 \leq a_i,b_i \leq n$,
• $m_i \leq 100000$
• 时间限制：$1000\mathrm{ms}$
• 空间限制：$262144\mathrm{KB}$