{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"4 5\n1 2 1\n1 3 1\n1 4 1\n3 2 2\n4 2 2"},{"iden":"sample output 1","content":"4\n\nRemoving Edges $4$ and $5$ yields a total reward of $4$. You cannot get any more, so the answer is $4$."},{"iden":"sample input 2","content":"3 3\n1 2 1\n2 3 0\n3 1 -1"},{"iden":"sample output 2","content":"1\n\nThere may be edges that give a negative reward when removed."},{"iden":"sample input 3","content":"2 3\n1 2 -1\n1 2 2\n1 1 3"},{"iden":"sample output 3","content":"5\n\nThere may be multi-edges and self-loops."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}