OI题库

【题目描述】

最近，RCDH研究外星人的交流方式很特别。它们会设置一个交流网。网络由n个站点组成，用双向的线连接。两个站点之间最多只能有一条线直接连接，同时每个站点最多只能和10个站点直接连接，但是任意两个站点之间必须存在一条路径将它们连接一起。每条传输线都有一个固定的传输速度。L（V，W）表示站点V和W之间的最短路径长度，且对任意的V有L（V，V）=0。

    外星人对每个站点的偏爱程度不同，所以有些站点的重要度会高一些。我们用R（V）表示站点V的重要程度（Imp）。Imp越高站点越重要。

    每个站点都会存储周围站点的信息，以防丢失。当然站点的空间有限，不会存储所有的站点信息，只有通过它们自己的人工智能判断后感觉有兴趣的才会存储。站点V对站点W感兴趣是指，不存在站点U满足：R（U）>R（W）且L（V，U）<=（V，W）。

    举个例子来说明，所有具有最高Imp的站点都会被别的站点感兴趣。如果V是一个具有最高Imp的站点，由于L（V，V）=0，所以V只对具有最高Imp的站点感兴趣。我们定义B（V）为V感兴趣的站点的集合。

    外星人希望计算所有站点的信息量，即所有站点的│B（V）│之和。火星人并不希望存储太多的数据，所以所有站点存储的数据量（│B（V）│之和）不会超过30n。

 你的任务是写一个程序，读入外星人的站点网络分布，计算所有站点存储的数据量。

【输人格式】

第一行两个整数n和m。n表示站点的数量，m表示传输线的数量。

接下来n行，每行有一个整数，第I行的整数为R（I），表示第I个站点的Imp。

接下来m行，每行表示各传输线的信息，包含3个整数a，b，t，a和b是传输线所连接的两个站点的编号，t是传输线的长度。

【输出格式】

一个整数，表示所有站点存储的数据总量，即│B（V）│之和。

【输入样例】

6 5

4

2

3

2

2

4

1 2 1

2 3 1

3 4 1

4 5 1

5 6 1

【输出样例】

17

【数据规模】

    对于100%的数据

    1<=n<=30000

    1<=m<=5n

    1<=R(i)<=10

    1<=t<=1000

    1<=a,b<=n

    a≠b