Byteland Network Information Storage

Byteland Kingdom is building a large-scale network among its servers and intends to provide various services. The network consists of \( n \) servers connected by bidirectional links. There is at most one direct link between any two servers, and every server is connected to at most 10 other servers. Moreover, the network is connected (i.e. there exists a path between any two servers).

Each link has a fixed transmission speed. Let \( \delta(v,w) \) denote the shortest path distance between servers \( v \) and \( w \) (with \( \delta(v,v)=0 \) by definition).

Every server \( v \) has an importance level represented by \( r(v) \). A higher \( r(v) \) means the server is more important. Each server \( v \) stores information about some of the other servers it is interested in. A server \( v \) is said to be interested in server \( w \) if there is no server \( u \) such that \( r(u) > r(w) \) and \( \delta(v,u) \le \delta(v,w) \). In other words, \( w \) is interesting to \( v \) if \( r(w) \) is the maximum among all servers within distance \( \delta(v,w) \) from \( v \). We denote \( B(v) \) to be the set of servers that \( v \) is interested in.

Your task is to compute the total amount of information stored across all servers, i.e. compute \( \sum_{v} |B(v)| \). It is guaranteed that \( \sum_{v} |B(v)| \le 30n \).

inputFormat

The first line contains two integers \( n \) and \( m \) (the number of servers and links, respectively).

The second line contains \( n \) integers: \( r(1), r(2), \dots, r(n) \), where \( r(i) \) denotes the importance rank of server \( i \).

Each of the following \( m \) lines contains three integers \( u\), \( v \) and \( w \) indicating that there is a bidirectional link between servers \( u \) and \( v \) with transmission speed (or weight) \( w \).

You may assume that the network is connected, there exists at most one direct link between any two servers, and every server is directly connected to at most 10 other servers.

outputFormat

Output a single integer representing the total amount of information stored across all servers \( (\sum_{v=1}^{n} |B(v)|) \).

sample

3 3
10 20 30
1 2 1
2 3 1
1 3 2

6