SP119 SERVERS - Servers

比特兰王国计划建立一个由多个服务器组成的大型计算机网络，提供多种服务。 这个网络由 $n$ 个服务器和多条双向线路构成。每对服务器之间最多可以直接相连一条线路。每台服务器最多与其他 $10$ 台服务器直接相连，并且网络中任意两台服务器都可以通过某种路径连通。每条线路都有固定的正向数据传输时间（以毫秒为单位）。定义服务器 $V$ 和 $W$ 之间的距离 $D(V, W)$ 为连接 $V$ 和 $W$ 的最短路径的传输时间。方便起见，我们规定 $D(V, V) = 0$ 对于任何服务器 $V$ 都成立。 某些服务器提供的服务比其他服务器更多，因此每个服务器 $V$ 被赋予一个自然数 $r(V)$，我们称之为等级。等级越高的服务器，功能越强大。 在每个服务器上，需要存储关于周边服务器的数据，但并不是所有服务器都值得记录。对于距离较远且等级较低的服务器，可以不储存其数据。具体而言，如果对于每个和服务器 $V$ 距离不超过 $W$ 的服务器 $U$，都满足 $r(U) \le r(W)$，那么服务器 $W$ 就被认为对服务器 $V$ 是有趣的。 比如，所有具有最高等级的服务器对其他所有服务器都是有趣的。如果某个服务器 $V$ 是最高等级，那么只有那些同样是最高等级的服务器对 $V$ 是有趣的。记 $B(V)$ 为对服务器 $V$ 有趣的服务器集合。 我们的任务是计算整个网络中需要存储的服务器数据总量，这个总量是所有集合 $B(V)$ 的大小之和。比特兰王国希望这个数据总量较小，因此设计了网络，使得这个总和不会超过 $30 \times n$。 ### 任务 编写一个程序来完成以下功能： - 从标准输入读取服务器网络的描述； - 计算整个网络中需要存储的服务器数据总量； - 将结果输出到标准输出。

输入的第一行为一个整数 $z$，表示测试用例的数量。接下来是 $z$ 个测试用例。 每个测试用例的第一行有两个自然数 $n$ 和 $m$，分别表示网络中的服务器数量（$1 \le n \le 30000$）和线路数量（$1 \le m \le 5n$）。这些数字由单个空格分隔。 接下来的 $n$ 行分别给出每个服务器的等级。第 $i$ 行包含一个整数 $r_i$（$1 \le r_i \le 10$），表示第 $i$ 台服务器的等级。 接下来的 $m$ 行描述了线路。每条线路由三个整数 $a$、$b$ 和 $t$ 组成（$1 \le t \le 1000$，$1 \le a, b \le n$，且 $a \neq b$），其中 $a$ 和 $b$ 表示线路连接的服务器，$t$ 是该线路的传输时间（以毫秒为单位）。

对于每个测试用例，输出一个整数，表示整个网络中需要存储的服务器数据总量。 **本翻译由 AI 自动生成**