题目描述

Byteland王国需要建立一个大型服务器网络。网络包含$n$个通过双向线路连接的服务器，满足：

1. 任意两台服务器之间最多一条直接连接
2. 每个服务器最多连接$10$个其他服务器
3. 网络全连通
4. 每条线路有固定的正数传输时延（毫秒）

定义$d(V,W)$为服务器$V$与$W$之间的最短传输时延（$d(V,V)=0$）。每个服务器$V$具有等级$r(V)$（自然数，等级越高性能越强）。

对于服务器$V$，定义其感兴趣服务器集合$B(V)$为满足以下条件的服务器$W$：

对所有满足$d(V,U) \leq d(V,W)$的服务器$U$，都有$r(U) \leq r(W)$

要求计算所有服务器$B(V)$集合的大小之和（保证不超过$30n$）。

输入格式

• 第一行：$n$（服务器数量，$1 \leq n \leq 30000$）和$m$（线路数量，$1 \leq m \leq 5n$）
• 接下来$n$行：每行一个整数$r_i$表示服务器$i$的等级（$1 \leq r_i \leq 10$）
• 接下来$m$行：每行三个整数$a,b,t$表示连接服务器$a$和$b$的线路时延（$11 \leq t \leq 1000$）

输出格式

一个整数，表示所有$B(V)$集合的大小之和

样例输入

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

样例输出

9

样例解释

$B(1)=\{1,2\},\ B(2)=\{2\},\ B(3)=\{2,3\},\ B(4)=\{1,2,3,4\}$，总和为$2+1+2+4=9$

题目来源

2002年西南欧地区竞赛