描述

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模拟赛