题目描述

$N$ 頂点 $M$ 辺の連結な無向グラフがあります。 頂点には $1$ から $N$ までの番号が、辺には $1$ から $M$ までの番号がついています。 また、各頂点、各辺にはそれぞれ重みが定められています。 頂点 $i$ の重みは $X_i$ です。 辺 $i$ は頂点 $A_i$ と $B_i$ を結ぶ辺で、その重みは $Y_i$ です。

グラフから辺を $0$ 本以上削除して、次の条件が満たされるようにしたいです。

• 削除されていない任意の辺について、その辺を含む連結成分の頂点の重みの総和が、その辺の重み以上である。

最小で何本の辺を消す必要があるかを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$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$

输出格式

最小で何本の辺を消す必要があるかを出力せよ。

题目大意

有一张 $n$ 个点 $m$ 条边的无向图，节点 $i$ 有点权$\ {x_i}$ ，边 $i$ 连接点$\ {a_i}$ 和 $\ {b_i}$ ，且有边权$\ {y_i}$ 。

现在要删除若干条边，使得剩下的图满足：对于没有被移除的边，其所在联通块中的点的点权和不小于该边的边权。

求需要移除的最小边数。

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

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

4

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

8

提示

制約

• $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$)
• 与えられるグラフは連結である。
• 入力される値はすべて整数である。

Sample Explanation 1

辺 $3,4$ を削除したとします。 このとき、辺 $1$ を含む連結成分は、頂点 $1,2,3$ からなる連結成分であり、頂点の重みの総和は $2+3+5=10$ です。 辺 $1$ の重みは $7$ なので、辺 $1$ については条件を満たしています。 また同様に、辺 $2$ についても条件を満たしています。 よって、辺を $2$ 本削除することで条件を満たすグラフが得られます。 辺を $1$ 本以下削除することによって条件を満たすことはできないので、答えは $2$ になります。