D - City Network Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

ある国には N 個の都市があり、それぞれ 1 から N の番号が付けられています。各都市には代表者が 1 人ずついて、都市 i の代表者を 代表者 i と呼びます。代表者 i と都市 i は一対一に対応しています。

この国には M 本の道路があり、各道路は双方向に通行できます。k 番目(1 \leq k \leq M)の道路は都市 U_k と都市 V_k を結び、通過にかかる時間は W_k です。同じ都市の組を結ぶ道路は高々 1 本であり、ある都市からそれ自身への道路(自己ループ)は存在しません。また、すべての都市の組が道路で行き来できるとは限りません(グラフは連結であるとは限りません)。

異なる 2 つの都市 i, j(i \neq j)について、都市 i から都市 j への最短移動時間を d(i, j) と定めます。道路をたどって都市 i から都市 j へ到達できない場合は d(i, j) = \infty とします。道路の辺重みはすべて正であるため最短移動時間は常に well-defined であり、道路は双方向に通行できるので、つねに d(i, j) = d(j, i) が成り立ちます。

各代表者 i には忍耐力 S_i(正整数)が定められています。代表者 i は、自分以外の都市 j(j \neq i)について、最短移動時間 d(i, j) が忍耐力 S_i 以下であるとき、都市 j に対して 不満を抱かない ものとします。逆に d(i, j) > S_i であるとき、都市 j に対して 不満を抱く ものとします。S_i は有限の正整数であるため、到達できない都市(d(i,j) = \infty)に対しては必ず不満を抱くことに注意してください。

代表者 i の 不満の個数 C_i を次のように定義します:

C_i = |\{ \, j \mid j \neq i, \; d(i, j) > S_i \, \}|

すなわち、C_i は代表者 i が不満を抱く都市の個数です。

高橋君はこの国の調査を行っており、各代表者の不満の個数をもとに、次のような分析をしたいと考えました。

異なる 2 人の代表者の組 (i, j)(i < j)が以下の条件をすべて満たすとき、この組を 友好ペア と呼びます:

  • d(i, j) \leq S_i かつ d(i, j) \leq S_j(すなわち、代表者 i は都市 j に対して不満を抱いておらず、かつ代表者 j も都市 i に対して不満を抱いていない)
  • C_i = C_j(不満の個数が等しい)

友好ペアの総数を求めて出力してください。

制約

  • 1 \leq N \leq 400
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq S_i \leq 10^9(1 \leq i \leq N)
  • 1 \leq U_k, V_k \leq N(1 \leq k \leq M)
  • U_k \neq V_k(1 \leq k \leq M)
  • 1 \leq W_k \leq 10^9(1 \leq k \leq M)
  • 同じ都市の組 \{U_k, V_k\} を結ぶ道路は高々 1 本である
  • 入力はすべて整数である

入力

N M
S_1 S_2 \ldots S_N
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 1 行目には、都市の数 N と道路の本数 M がスペース区切りで与えられる。
  • 2 行目には、各代表者の忍耐力 S_1, S_2, \ldots, S_N がスペース区切りで与えられる。
  • 続く M 行のうち k 行目(1 \leq k \leq M)には、k 番目の道路が結ぶ 2 つの都市の番号 U_k, V_k と通過にかかる時間 W_k がスペース区切りで与えられる。

出力

友好ペアの総数を 1 行で出力せよ。


入力例 1

4 4
3 3 3 3
1 2 1
2 3 1
3 4 1
1 3 2

出力例 1

6

入力例 2

2 0
1 1

出力例 2

0

入力例 3

6 7
5 5 5 5 5 5
1 2 2
2 3 2
3 4 2
4 5 2
5 6 2
1 4 5
2 5 5

出力例 3

3

入力例 4

10 15
10 10 10 10 10 10 10 10 10 10
1 2 3
2 3 3
3 4 3
4 5 3
5 6 3
6 7 3
7 8 3
8 9 3
9 10 3
1 5 11
2 6 11
3 7 11
4 8 11
5 9 11
6 10 11

出力例 4

6

入力例 5

1 0
1000000000

出力例 5

0

Score : 400 pts

Problem Statement

A country has N cities, numbered from 1 to N. Each city has exactly one representative, and the representative of city i is called representative i. Representative i and city i are in one-to-one correspondence.

The country has M roads, each of which can be traversed in both directions. The k-th road (1 \leq k \leq M) connects city U_k and city V_k, and takes time W_k to traverse. There is at most one road connecting any pair of cities, and there are no roads from a city to itself (no self-loops). Furthermore, it is not guaranteed that all pairs of cities can reach each other via roads (the graph is not necessarily connected).

For two distinct cities i, j (i \neq j), let d(i, j) denote the shortest travel time from city i to city j. If city j cannot be reached from city i by following roads, then d(i, j) = \infty. Since all edge weights are positive, the shortest travel time is always well-defined, and since roads can be traversed in both directions, d(i, j) = d(j, i) always holds.

Each representative i has a patience value S_i (a positive integer). Representative i is not dissatisfied with city j (j \neq i) if the shortest travel time d(i, j) is at most their patience S_i. Conversely, if d(i, j) > S_i, representative i is dissatisfied with city j. Note that since S_i is a finite positive integer, a representative is always dissatisfied with any unreachable city (where d(i,j) = \infty).

The dissatisfaction count C_i of representative i is defined as follows:

C_i = |\{ \, j \mid j \neq i, \; d(i, j) > S_i \, \}|

In other words, C_i is the number of cities that representative i is dissatisfied with.

Takahashi is conducting a survey of this country and wants to perform the following analysis based on each representative's dissatisfaction count.

A pair of two distinct representatives (i, j) (i < j) is called a friendly pair if it satisfies all of the following conditions:

  • d(i, j) \leq S_i and d(i, j) \leq S_j (that is, representative i is not dissatisfied with city j, and representative j is not dissatisfied with city i)
  • C_i = C_j (their dissatisfaction counts are equal)

Find and output the total number of friendly pairs.

Constraints

  • 1 \leq N \leq 400
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_k, V_k \leq N (1 \leq k \leq M)
  • U_k \neq V_k (1 \leq k \leq M)
  • 1 \leq W_k \leq 10^9 (1 \leq k \leq M)
  • There is at most one road connecting the same pair of cities \{U_k, V_k\}
  • All input values are integers

Input

N M
S_1 S_2 \ldots S_N
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • The first line contains the number of cities N and the number of roads M, separated by a space.
  • The second line contains the patience values S_1, S_2, \ldots, S_N of each representative, separated by spaces.
  • The following M lines each contain, for the k-th road (1 \leq k \leq M), the two city numbers U_k, V_k connected by the road and the travel time W_k, separated by spaces.

Output

Output the total number of friendly pairs in a single line.


Sample Input 1

4 4
3 3 3 3
1 2 1
2 3 1
3 4 1
1 3 2

Sample Output 1

6

Sample Input 2

2 0
1 1

Sample Output 2

0

Sample Input 3

6 7
5 5 5 5 5 5
1 2 2
2 3 2
3 4 2
4 5 2
5 6 2
1 4 5
2 5 5

Sample Output 3

3

Sample Input 4

10 15
10 10 10 10 10 10 10 10 10 10
1 2 3
2 3 3
3 4 3
4 5 3
5 6 3
6 7 3
7 8 3
8 9 3
9 10 3
1 5 11
2 6 11
3 7 11
4 8 11
5 9 11
6 10 11

Sample Output 4

6

Sample Input 5

1 0
1000000000

Sample Output 5

0