描述

S国的网络系统由N个城市服务点和M条双向传输光缆构成。每个城市有一个评级Ri。每条光缆有一个传输时间Ti。我们规定d(i,j)为城市i到城市j的最短传输时间(我们认为d(i,i)=0)。现在城市之间有一种单向合作意愿。我们说城市B愿意与城市A建立合作关系,当且仅当对于所有满足d(A,C)<=d(A,B)的城市C,都有R(C)<=R(B)。一个城市的受欢迎程度Bi定义为愿意与其建立合作关系的城市数量。现在S国政府想知道所有城市的受欢迎程度之和Sum是多少。由于S国的网络系统规模有限,可以向你保证每个城市连接的光缆数目不超过10条,所有城市的受欢迎程度之和不超过30N。

输入格式

第一行包含两个用空格隔开的整数,N和M。
接下来N行表示每个城市的评级Ri。
接下来M行,每行三个整数,Xi、Yi、Ti表示城市Xi和城市Yi之间有一条双向传输光缆,传输时间为Ti。

输出格式

输出一个整数,表示所有城市的受欢迎程度之和Sum。

样例输入

4 3
2
3
1
1
1 4 30
2 3 20
3 4 20

样例输出

9

数据范围与约定

  • 对于10%的数据,满足N<=100。
  • 对于40%的数据,满足N<=1000。
  • 对于100%的数据,满足N<=30000,1<=M<=5N,1<=Ri<=10,1<=Ti<=1000,Sum<=30N。

来源

【Nescafé 31】杯NOIP模拟赛