Spiderman has trapped Doctor Strange in his own world using his geometry skills. But Doctor Strange needs to escape soon to save Spiderman and others on Earth. He has asked Deepanshu to help him in return of some reward.
The web he is trapped in is like 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 Ui and Vi.
Deepanshu is going to remove zero or more edges from this graph.
When removing Edge i, a reward of Wi is given if Wi >= 0, and a fine of ∣Wi∣ is incurred if Wi < 0.
Find the maximum total reward that Deepanshu can get when the graph must be connected after removing edges.
Input Format:-
- First line contains two integers N and M.
- Next M lines contains 3 integers:
- Ui Vi Wi
Output Format:-
- Print the required answer.
Constraints:-
- 2≤N≤2∗105
- N−1≤M≤2∗105
- 1≤Ui,Vi≤N
- −10−9≤Wi≤109
Removing Edges 4 and 5 yields a total reward of 4. You cannot get any more, so the answer is 4.
