15131513 SUSTech Online Judge

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

## Description

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.

## Input

$$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$$

## Sample Input

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


## Sample Output

1


[Submit][Status]