翻訳済みドキュメント

世界は $n$ 個の都市と $m$ 本の交通路からなる連結グラフである。各交通路には重みが設定されている。ある連結部分グラフの重み $w(s)$ を、その部分グラフの最小全域木の重みの総和と最大全域木の重みの総和の排他的論理和（XOR）と定義する。

注意：

• $w(s)$ はグラフ $G$ の連結部分グラフ $(s, E_s)$ に対してのみ定義される。
• 連結部分グラフ $(s, E_s)$ において、頂点集合を $s$、辺集合 $E_s = \{(u, v) \in E \mid u, v \in s\}$ を両端点が $s$ に含まれるすべての辺の集合とする。連結とは、$s$ 内の任意の2点が $E_s$ に含まれる辺によって連結可能であることを指す。

あなたは最初、1つの都市を選んで発展を開始できる。現在感染している都市の集合を $S$ とし、次のステップで拡張する集合を $T$ とする（$S \subset T$ かつ $T$ が連結であることを満たす必要がある）。このとき、このステップでの DNA ポイント消費量は $(|T| - |S|) \times w(T)$ となる。

感染計画、すなわち頂点集合の列 $S_1 \subset S_2 \subset \dots \subset S_k$ を見つけよ。ここで $S_1$ は1つの都市のみを含み、$S_k$ はすべての都市を含み、各ステップで集合が連結であることを保証するものとする。このとき、拡張にかかる総 DNA ポイント消費量を最小化せよ。

入力

入力の1行目には、2つの正整数 $n, m$ が与えられる。これらは都市の数と道路の数を表す。

続く $m$ 行には、それぞれ3つの正整数 $u, v, w$ が与えられ、1本の交通路を表す。

出力

最小の DNA コストを1行で出力せよ。

入出力例

入力 1

3 3
1 2 1
2 3 2
1 3 3

出力 1

6

入力 2

配布ファイルを参照のこと

出力 2

配布ファイルを参照のこと

入力 3

配布ファイルを参照のこと

出力 3

配布ファイルを参照のこと

サブタスク

すべてのデータにおいて、$1 \le n \le 20, 1 \le m \le 100, 1 \le w \le 10000$ であり、グラフは連結であることが保証される。

サブタスク1（20点）：$n \le 3, m \le 10$

サブタスク2（10点）：$n \le 4, m \le 10$

サブタスク3（10点）：$n \le 5, m \le 10$

サブタスク4（20点）：$n \le 10, m \le 100$

サブタスク5（20点）：$n \le 16, m \le 100$

サブタスク6（20点）：$n \le 20, m \le 100$