Dango氏の家は想像を絶する大家族である。昔はおよそ100人の家族だったのだが、 今では一つの街を作れるほど巨大になり、 もうすぐこの星を埋め尽くすのではないか、なんていう冗談も囁かれている。
そんなDango氏の家族だが、 現在、新居を建設中である。 それこそ、 一つの街のような恐ろしい規模の建物である。
彼らは皆穏やかで優しい性格をしていて家族全員仲良しであったのだが、 今年になってからある二人の仲がとてもとても険悪になってしまったのである。 そして、 この二人は家族内でとても影響力を持っていたことから家族は二つの勢力に二分されてしまったのである。
彼らはこの二つの勢力が新居ではどうやっても居合わせることが無いことを望んでいる。 建物は一緒でも部屋同士を繋ぐ通路を工夫すればそれも可能である。
今、建設中の新居の設計図が手元にある。 あなたの仕事は以下の内容である。
あなたはそれぞれの部屋についてどちらの勢力に属するか決めなければならない。 加えて、 片方の勢力に属するどんな部屋からでも、もう片方の部屋への移動を不可能にしなければならない。 すべての部屋はちょうど一つの勢力に属さなければならない。 ただし、両勢力は少なくとも一つの部屋を所持していなければならない。
あなたはこの仕事の達成ために、建設中の通路の建設を取りやめる権利も持っている。 新居は建設中であるため通路の建設を取り消すためにはそれぞれ通路によるコストがかかる。 部屋の数と通路についての情報を得たあなたは、最小のコストでこの仕事を達成しなければならない。 最小のコストを求めよ。
Dango氏一族はその一族の特徴から、通路の移動にとても時間がかかる。 よって、 通路は全てエスカレーターで作られている。 そのことから、 通路は一方通行である。
複数のデータセットが与えられる。 各データセットは以下の形式で与えられる。
n m X1 Y1 C1 ... Xm Ym Cm
データセット中のすべての数は整数である。 行中の整数の区切りはすべて空白一個である。
データセットの最初の行は二つの整数を含んでいる。 n , m はそれぞれこの家の部屋の数、通路の数を表している。 各部屋には0からn-1までの番号が付いている。
続く m 行では通路の情報が与えられる。 各行では三つの整数が与えられる。 一つ目の整数 Xi は通路の始点の部屋の番号を表す。 二つ目の整数 Yi は通路の終点の部屋の番号を表す。 三つ目の整数 Ci はその通路の建設を中止するためのコストを表す。 通路であるエスカレーターは始点から終点へしか移動することができない。 入力の終了は0を二つ含む行で示される。
各データセットについて、最小のコストを1行に出力せよ。 答えの数値はすべて、32bit signed integer に収まると仮定してよい。
3 2 0 1 2 1 2 1 2 1 0 1 100 2 1 0 1 0 2 1 0 1 -1 0 0
1 100 0 -1