题目描述

$N$ 頂点 $M$ 辺の連結無向グラフがあります。
頂点には $1$ から $N$ の番号が、辺には $1$ から $M$ の番号がついており、辺 $i$ は頂点 $A_i$ と $B_i$ を結んでいます。

高橋君は、このグラフから $0$ 個以上の辺を取り除こうとしています。

辺 $i$ を取り除くと、$C_i\ \geq\ 0$ のとき $C_i$ の報酬を得、$C_i\ <\ 0$ のとき $|C_i|$ の罰金を払います。

辺を取り除いたあともグラフが連結でなければならないとき、高橋君が得られる報酬の最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_M$ $B_M$ $C_M$

输出格式

答えを出力せよ。

题目大意

给一个无向图，让你从中选出几个边，要求选出的边权总和最大并且剩下的图要是一个连通图，输出最大的边权。

4 5
1 2 1
1 3 1
1 4 1
3 2 2
4 2 2

4

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

1

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

5

提示

制約

• $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$
• 与えられるグラフは連結である
• 入力に含まれる値は全て整数である

Sample Explanation 1

辺 $4,5$ を取り除くことで合計 $4$ の報酬を得られます。これより多くの報酬を得ることはできないため、答えは $4$ となります。

Sample Explanation 2

報酬が負であるような辺が存在することもあります。

Sample Explanation 3

多重辺や自己ループが存在することもあります。