/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 頂点 M 辺の連結無向グラフがあります。
頂点には 1 から N の番号が、辺には 1 から M の番号がついており、辺 i は頂点 A_i と B_i を結んでいます。
高橋君は、このグラフから 0 個以上の辺を取り除こうとしています。
辺 i を取り除くと、C_i \geq 0 のとき C_i の報酬を得、C_i<0 のとき |C_i| の罰金を払います。
辺を取り除いたあともグラフが連結でなければならないとき、高橋君が得られる報酬の最大値を求めてください。
制約
- 2 \leq N \leq 2\times 10^5
- N-1 \leq M \leq 2\times 10^5
- 1 \leq A_i,B_i \leq N
- -10^9 \leq C_i \leq 10^9
- 与えられるグラフは連結である
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
出力
答えを出力せよ。
入力例 1
4 5 1 2 1 1 3 1 1 4 1 3 2 2 4 2 2
出力例 1
4
辺 4,5 を取り除くことで合計 4 の報酬を得られます。これより多くの報酬を得ることはできないため、答えは 4 となります。
入力例 2
3 3 1 2 1 2 3 0 3 1 -1
出力例 2
1
報酬が負であるような辺が存在することもあります。
入力例 3
2 3 1 2 -1 1 2 2 1 1 3
出力例 3
5
多重辺や自己ループが存在することもあります。
Score : 500 points
Problem Statement
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.
Takahashi is going to remove zero or more edges from this graph.
When 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.
Find the maximum total reward that Takahashi can get when the graph must be connected after removing edges.
Constraints
- 2 \leq N \leq 2\times 10^5
- N-1 \leq M \leq 2\times 10^5
- 1 \leq A_i,B_i \leq N
- -10^9 \leq C_i \leq 10^9
- The given graph is connected.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
Output
Print the answer.
Sample Input 1
4 5 1 2 1 1 3 1 1 4 1 3 2 2 4 2 2
Sample Output 1
4
Removing Edges 4 and 5 yields a total reward of 4. You cannot get any more, so the answer is 4.
Sample Input 2
3 3 1 2 1 2 3 0 3 1 -1
Sample Output 2
1
There may be edges that give a negative reward when removed.
Sample Input 3
2 3 1 2 -1 1 2 2 1 1 3
Sample Output 3
5
There may be multi-edges and self-loops.