配点 : $800$ 点

問題文

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

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

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

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

制約

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

入力

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

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

出力

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

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

2

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

辺を $1$ 本以下削除することによって条件を満たすことはできないので、答えは $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