Servers

The Kingdom of Byteland decided to develop a large computer network of servers offering various services.

The network is built of $n$ servers connected by bidirectional cables. Two servers can be directly connected by at most one cable, and each server can be directly connected to at most $10$ other servers. Moreover, every two servers are connected by some path in the network (the network is connected). Each cable has a fixed positive data transmission time measured in milliseconds.

The distance $d(V, W)$ between two servers $V$ and $W$ is the length (in milliseconds) of the shortest path — the one with the smallest total transmission time — connecting them. For convenience we set $d(V, V) = 0$ for every $V$.

Each server $V$ is labelled with a natural number $r(V)$ called its rank. The larger the rank, the more powerful the server.

Every server must store information about nearby servers, but not about all of them: information about distant, low-rank servers need not be stored. Precisely, a server $W$ is interesting for a server $V$ if for every server $U$ with $d(V, U) \le d(V, W)$ we have $r(U) \le r(W)$.

For example, every server of the maximum rank is interesting for all servers. If a server $V$ has the maximum rank, then exactly the servers of the maximum rank are interesting for $V$. Let $B(V)$ denote the set of servers interesting for $V$.

We want to compute the total amount of information that must be stored in the network, i.e. the sum of the sizes of all sets $B(V)$, namely $\sum_V |B(V)|$. The kingdom built the network so that this sum never exceeds $30n$.

Write a program that reads the description of the network from standard input, computes this total, and writes it to standard output.

The first line contains two natural numbers $n$ and $m$ separated by a single space, where $n$ is the number of servers ($1 \le n \le 30000$) and $m$ is the number of cables ($1 \le m \le 5n$).

Each of the next $n$ lines contains one integer $r_i$ ($1 \le r_i \le 10$) — the rank of the $i$-th server.

Each of the following $m$ lines describes one cable with three integers $a$, $b$, $t$ ($1 \le a, b \le n$, $a \ne b$, $11 \le t \le 1000$): $a$ and $b$ are the servers joined by the cable and $t$ is its transmission time in milliseconds.

Output a single integer equal to the total amount of information that must be stored in the network.

For the four-server network with ranks $2, 3, 1, 1$, the total is $9$ because $B(1) = {1, 2}$, $B(2) = {2}$, $B(3) = {2, 3}$, and $B(4) = {1, 2, 3, 4}$.