서버

바이트랜드 왕국은 여러 가지 서비스를 제공하는 대규모 서버 컴퓨터 네트워크를 구축하기로 했습니다.

이 네트워크는 $n$개의 서버가 양방향 케이블로 연결되어 이루어집니다. 두 서버는 최대 하나의 케이블로만 직접 연결될 수 있고, 각 서버는 최대 $10$개의 다른 서버와 직접 연결됩니다. 또한 임의의 두 서버는 네트워크 상의 어떤 경로로든 서로 연결되어 있습니다(즉, 연결 그래프입니다). 각 케이블에는 밀리초 단위의 양의 데이터 전송 시간이 정해져 있습니다.

두 서버 $V$와 $W$ 사이의 거리 $d(V, W)$는 두 서버를 잇는 경로 중 전송 시간의 합이 가장 작은(최단) 경로의 길이(밀리초)로 정의합니다. 편의상 모든 $V$에 대해 $d(V, V) = 0$으로 둡니다.

각 서버 $V$에는 자연수 $r(V)$가 매겨져 있으며, 이를 등급(rank)이라고 합니다. 등급이 높을수록 더 강력한 서버입니다.

각 서버는 주변 서버들에 대한 정보를 저장해야 하지만, 모든 서버가 저장 대상은 아닙니다. 멀리 있으면서 등급이 낮은 서버의 정보는 저장할 필요가 없습니다. 정확히 말하면, 서버 $W$가 서버 $V$에게 흥미로운(interesting) 서버라는 것은 $d(V, U) \le d(V, W)$를 만족하는 모든 서버 $U$에 대해 $r(U) \le r(W)$가 성립하는 것을 뜻합니다.

예를 들어, 최대 등급을 가진 서버는 모든 서버에게 흥미롭습니다. 만약 서버 $V$가 최대 등급이라면, $V$에게 흥미로운 서버는 정확히 최대 등급을 가진 서버들뿐입니다. $B(V)$를 서버 $V$에게 흥미로운 서버들의 집합이라고 합시다.

네트워크 전체에서 저장해야 하는 서버 정보의 총량, 즉 모든 집합 $B(V)$의 크기의 합 $\sum_V |B(V)|$을 구하려고 합니다. 바이트랜드 왕국은 이 값이 $30n$을 넘지 않도록 네트워크를 구성했습니다.

표준 입력으로 서버 네트워크의 정보를 읽어, 저장해야 하는 서버 정보의 총량을 계산한 뒤 표준 출력으로 출력하는 프로그램을 작성하세요.

첫째 줄에 두 자연수 $n$, $m$이 공백 하나로 구분되어 주어집니다. $n$은 네트워크의 서버 수($1 \le n \le 30000$), $m$은 케이블의 수($1 \le m \le 5n$)입니다.

다음 $n$개의 줄에는 각 서버의 등급이 주어집니다. $i$번째 줄에는 정수 $r_i$($1 \le r_i \le 10$), 즉 $i$번 서버의 등급이 하나씩 주어집니다.

그다음 $m$개의 줄에는 케이블의 정보가 주어집니다. 각 케이블은 세 정수 $a$, $b$, $t$($1 \le a, b \le n$, $a \ne b$, $11 \le t \le 1000$)로 표현되며, $a$와 $b$는 케이블이 연결하는 두 서버의 번호, $t$는 그 케이블의 전송 시간(밀리초)입니다.

네트워크에서 저장해야 하는 서버 정보의 총량과 같은 정수 하나를 출력합니다.

등급이 각각 $2, 3, 1, 1$인 네 서버로 이루어진 네트워크에서는 $B(1) = \{1, 2\}$, $B(2) = \{2\}$, $B(3) = \{2, 3\}$, $B(4) = \{1, 2, 3, 4\}$이므로 저장해야 하는 정보의 총량은 $9$입니다.