Problem Description

There is a connected undirected graph with $ N $ vertices and $ M $ edges. The vertices are numbered from $ 1 $ to $ N $, and the edges are numbered from $ 1 $ to $ M $. Each vertex and each edge has a weight assigned to it. The weight of vertex $ i $ is $ X_i $. Edge $ i $ connects vertices $ A_i $ and $ B_i $, and its weight is $ Y_i $.

We want to delete zero or more edges from the graph such that the following condition is satisfied:

• For any undeleted edge, the sum of the weights of the vertices in the connected component containing that edge is at least the weight of that edge.

Determine the minimum number of edges that need to be deleted.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ X_1 $ $ X_2 $ $ ... $ $ X_N $ $ A_1 $ $ B_1 $ $ Y_1 $ $ A_2 $ $ B_2 $ $ Y_2 $ $ : $ $ A_M $ $ B_M $ $ Y_M $

Output Format

Output the minimum number of edges that need to be deleted.

Sample Input and Output

Sample Input #1

4 4
2 3 5 7
1 2 7
1 3 9
2 3 12
3 4 18

Sample Output #1

2

Sample Input #2

6 10
4 4 1 1 1 7
3 5 19
2 5 20
4 5 8
1 6 16
2 3 9
3 6 16
3 4 1
2 6 20
2 4 19
1 2 9

Sample Output #2

4

Sample Input #3

10 9
81 16 73 7 2 61 86 38 90 28
6 8 725
3 10 12
1 4 558
4 9 615
5 6 942
8 9 918
2 7 720
4 7 292
7 10 414

Sample Output #3

8

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $N-1 \leq M \leq 10^5$
• $1 \leq X_i \leq 10^9$
• $1 \leq A_i < B_i \leq N$
• $1 \leq Y_i \leq 10^9$
• $(A_i, B_i) \neq (A_j, B_j)$ ($i \neq j$)
• The given graph is connected.
• All input values are integers.

Sample Explanation 1

If we delete edges $ 3 $ and $ 4 $. The connected component containing edge $ 1 $ consists of vertices $ 1, 2, 3 $, and the sum of their weights is $ 2 + 3 + 5 = 10 $. The weight of edge $ 1 $ is $ 7 $, so the condition is satisfied for edge $ 1 $. Similarly, the condition is satisfied for edge $ 2 $. Thus, by deleting $ 2 $ edges, we can satisfy the condition. It is not possible to satisfy the condition by deleting $ 1 $ or fewer edges, so the answer is $ 2 $.

见题面 Input 部分

见题面 Output 部分