{"problem":{"name":"Destruction","description":{"content":"We have a connected undirected graph with $N$ vertices and $M$ edges.   The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$. Edge $i$ connects Vertices $A_i$ and $B_i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc218_e"},"statements":[{"statement_type":"Markdown","content":"We have a connected undirected graph with $N$ vertices and $M$ edges.  \nThe vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$. Edge $i$ connects Vertices $A_i$ and $B_i$.\nTakahashi is going to remove zero or more edges from this graph.\nWhen removing Edge $i$, a reward of $C_i$ is given if $C_i \\geq 0$, and a fine of $|C_i|$ is incurred if $C_i<0$.\nFind the maximum total reward that Takahashi can get when the graph must be connected after removing edges.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2\\times 10^5$\n*   $N-1 \\leq M \\leq 2\\times 10^5$\n*   $1 \\leq A_i,B_i \\leq N$\n*   $-10^9 \\leq C_i \\leq 10^9$\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$A_1$ $B_1$ $C_1$\n$A_2$ $B_2$ $C_2$\n$\\vdots$\n$A_M$ $B_M$ $C_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc218_e","tags":[],"sample_group":[["4 5\n1 2 1\n1 3 1\n1 4 1\n3 2 2\n4 2 2","4\n\nRemoving Edges $4$ and $5$ yields a total reward of $4$. You cannot get any more, so the answer is $4$."],["3 3\n1 2 1\n2 3 0\n3 1 -1","1\n\nThere may be edges that give a negative reward when removed."],["2 3\n1 2 -1\n1 2 2\n1 1 3","5\n\nThere may be multi-edges and self-loops."]],"created_at":"2026-03-03 11:01:14"}}