青木くんは盆栽が好きで、いくつも盆栽を持っています。 ある朝青木くんが起きるとなんと、盆栽の一つが変な形になっていました。 枝の先同士が繋がっていたり、くるくる巻いていたりして、とても盆栽と呼べたものではありません。 青木くんは切断のプロ・高橋君に、木の形になるように最小の本数の枝を切って整えてもらうことにしました。
高橋君は枝を切るのが好きで、できるだけたくさんの枝を切りたいです。 しかし、青木くんは最小の本数と指定しているので、好き勝手に切ることはできません。 そこで高橋くんは、切った枝の長さの合計ができるだけ大きくなるように切ることにしました。
頂点 辺の連結な無向グラフが与えられます。 番目の辺は頂点 と を結び、長さは です。 このグラフから何本かの辺を取り除いて木にするとき、取り除いた辺の長さの合計を、最大でいくらにできるか答えてください。
N M u_1 v_1 l_1 ... u_M v_M l_M
答えを 行に出力せよ。
4 4 1 2 1 2 3 2 3 4 3 4 1 4
4
辺 を取り除くと合計は で、これが最大です。
6 7 1 2 2 1 3 3 1 4 1 2 5 3 3 6 2 4 5 2 4 6 4
7
辺 を取り除くと合計は で、これが最大です。
2 1 1 2 1333
0
取り除ける辺はありません。