removeedges

Shiwei city is a connected undirected graph with N cities and M roads, with cities numbered 1 to N and roads numbered from 1 to M. City i has a value of Xi and edge i has a values of Yi connecting node Ai and Bi.

Zane the (redacted) wants to remove some edges to make Shiwei happy. Specifically, Shiwei hopes that for each roads not removed, the sum of the values of the cities in the connected component containing that road is greater than or equal to the value of that roads.

Zane is lazy. Find the minimum number of edges that need to be removed.

Constraints

1 ≤ N ≤ 105
N-1 ≤ M ≤ 105
1 ≤ Xi, Yi ≤ 109
The given graph is connected.

Input Format

First line of input contains 2 integers N and M

Next line contains N integers representing X

Next M lines contain 3 integers, Ai, Bi, Yi

Output Format

Output the minimum number of roads Zane needs to destroy

Sample

Input:
4 4
2 3 5 7
1 2 7
1 3 9
2 3 12
3 4 18
Output:
2

Submitting .cpp to 'removeedges'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 2 Seconds
Memory Limit: 256MB
No. of ACs: 22
Your best score: 0
Source: Atcoder
Editorial: 1

Subtask Score
1 100
2 0