Description

The Kingdom of Byteland is preparing to build a large network among its servers and provide various services.

The network consists of $n$ servers, connected by bidirectional links. There is at most one direct link between any pair of servers. Each server is directly connected to at most $10$ servers. Furthermore, there is a path between any two servers.

Each transmission link has a fixed length. Let $\delta(v,w)$ denote the length of the shortest path between servers $v$ and $w$, and for any $v$ we have $\delta(v,v)=0$.

Some servers provide more services than others and are therefore more important. We use $r(v)$ to denote the importance $\texttt{rank}$ of server $v$. A higher $\texttt{rank}$ means a more important server.

Each server stores information about nearby servers. Of course, not all servers’ information is stored—only the interesting ones. Server $v$ is interested in server $w$ if there does not exist a server $u$ such that $r(u)>r(w)$ and $\delta(v,u)\le\delta(v,w)$.

For example, all servers with the highest $\texttt{rank}$ are interesting to every other server. If $v$ has the highest $\texttt{rank}$, then since $\delta(v,v)=0$, $v$ is interested only in servers with the highest $\texttt{rank}$.

We define $B(v)$ as the set of servers that server $v$ is interested in. We want to compute the total amount of information stored by all servers, i.e., the sum of $|B(v)|$ over all servers. Byteland does not want to store a large amount of data, so the total amount of stored data (the sum of $|B(v)|$) will not exceed $30n$.

Your task is to write a program that reads the network layout of Byteland and computes the total amount of information stored by all servers.

Input Format

The first line contains two integers $n$ and $m$. Here $n$ is the number of servers and $m$ is the number of transmission links.

The next $n$ lines each contain one integer. The integer on the $i$-th line is $r(i)$, the $\texttt{rank}$ of server $i$.

The next $m$ lines each describe a transmission link with three integers $a,b,t$. Here $a$ and $b$ are the indices of the two servers connected by the link, and $t$ is the length of the link.

Output Format

Output a single integer: the total amount of data stored by all servers, i.e., the sum of $|B(v)|$.

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

9

Hint

Output explanation:

$B(1)=\{1,2\},B(2)=\{2\},B(3)=\{2,3\},B(4)=\{1,2,3,4\}$.

Constraints:

$1\le n\le30000,1\le m\le5n$

$1\le r(i)\le 10$

$1\le t\le 1000,1\le a,b\le n,a\neq b$.

Translated by ChatGPT 5