15131513 SUSTech Online Judge
Problem 1513 --Sign in Problem

1513: Sign in Problem

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1058  Solved: 203
[Submit][Status][Web Board]


Given a connected undirected graph of \(n\) vertices with \(m\) edges (may with negative weights)(edge \(i\) connects vertices \(u_i, v_i\) and with weight \(w_i\)), you can perform edge deletion, where the gain from deleting an edge is the edge weight of that edge, but you need to ensure that the graph remains connected after performing the edge deletion operation.

Your goal is to maximize the sum of the gains from all operations.


\(1\leq n \leq 2\times 10^5\)

\(n-1\leq m \leq 2\times 10^5\)

\(1\leq u_i, v_i \leq n\)

\(-10^9\leq w_i\leq 10^9\)


Print one number as your answer

Sample Input

3 3
1 2 1
2 3 0
3 1 -1

Sample Output