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.


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


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

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