{"problem":{"name":"Weights on Vertices and Edges","description":{"content":"There is a connected undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$, and the edges are numbered $1$ to $M$. Also, each of these vertices and edges has a specifi","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"nikkei2019_qual_e"},"statements":[{"statement_type":"Markdown","content":"There is a connected undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$, and the edges are numbered $1$ to $M$. Also, each of these vertices and edges has a specified weight. Vertex $i$ has a weight of $X_i$; Edge $i$ has a weight of $Y_i$ and connects Vertex $A_i$ and $B_i$.\nWe would like to remove zero or more edges so that the following condition is satisfied:\n\n*   For each edge that is not removed, the sum of the weights of the vertices in the connected component containing that edge, is greater than or equal to the weight of that edge.\n\nFind the minimum number of edges that need to be removed.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^5$\n*   $N-1 \\leq M \\leq 10^5$\n*   $1 \\leq X_i \\leq 10^9$\n*   $1 \\leq A_i < B_i \\leq N$\n*   $1 \\leq Y_i \\leq 10^9$\n*   $(A_i,B_i) \\neq (A_j,B_j)$ ($i \\neq j$)\n*   The given graph is connected.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$X_1$ $X_2$ $...$ $X_N$\n$A_1$ $B_1$ $Y_1$\n$A_2$ $B_2$ $Y_2$\n$:$\n$A_M$ $B_M$ $Y_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"nikkei2019_qual_e","tags":[],"sample_group":[["4 4\n2 3 5 7\n1 2 7\n1 3 9\n2 3 12\n3 4 18","2\n\nAssume that we removed Edge $3$ and $4$. In this case, the connected component containing Edge $1$ contains Vertex $1, 2$ and $3$, and the sum of the weights of these vertices is $2+3+5=10$. The weight of Edge $1$ is $7$, so the condition is satisfied for Edge $1$. Similarly, it can be seen that the condition is also satisfied for Edge $2$. Thus, a graph satisfying the condition can be obtained by removing two edges.\nThe condition cannot be satisfied by removing one or less edges, so the answer is $2$."],["6 10\n4 4 1 1 1 7\n3 5 19\n2 5 20\n4 5 8\n1 6 16\n2 3 9\n3 6 16\n3 4 1\n2 6 20\n2 4 19\n1 2 9","4"],["10 9\n81 16 73 7 2 61 86 38 90 28\n6 8 725\n3 10 12\n1 4 558\n4 9 615\n5 6 942\n8 9 918\n2 7 720\n4 7 292\n7 10 414","8"]],"created_at":"2026-03-03 11:01:14"}}