AT_nikkei2019_qual_e Weights on Vertices and Edges

有一个包含 $N$ 个顶点、$M$ 条边的连通无向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。每个顶点和每条边都有一个权值。顶点 $i$ 的权值为 $X_i$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$，其权值为 $Y_i$。 你可以从图中删除 $0$ 条或多条边，使得满足以下条件： - 对于任意未被删除的边，该边所在的连通分量中所有顶点的权值之和不少于该边的权值。 请你求出，最少需要删除多少条边才能满足上述条件。

输入通过标准输入给出，格式如下： > $N$ $M$ $X_1$ $X_2$ $\ldots$ $X_N$ $A_1$ $B_1$ $Y_1$ $A_2$ $B_2$ $Y_2$ $\ldots$ $A_M$ $B_M$ $Y_M$

输出最少需要删除的边的数量。

## 限制条件 - $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$） - 给定的图是连通的。 - 输入的所有值均为整数。 ## 样例解释 1 假设删除了第 $3$ 条和第 $4$ 条边。此时，包含第 $1$ 条边的连通分量由顶点 $1,2,3$ 组成，这些顶点的权值之和为 $2+3+5=10$。第 $1$ 条边的权值为 $7$，因此第 $1$ 条边满足条件。同理，第 $2$ 条边也满足条件。因此，通过删除 $2$ 条边可以得到满足条件的图。无法通过删除 $1$ 条或更少的边来满足条件，所以答案为 $2$。 由 ChatGPT 4.1 翻译