世界是一個由 $n$ 個城市，$m$ 條交通路線組成的連通圖。每條交通路線有一個權值。定義一個連通子圖的權值 $w(s)$ 是子圖的最小生成樹權值和與最大生成樹權值和的異或和。

注意：

• $w(s)$ 僅對圖 $G$ 的連通子圖 $(s,E_s)$ 才有定義；
• 連通子圖 $(s,E_s)$，其中點集為 $s$，邊集 $E_s = \{(u,v)\in s\}$ 為所有兩端點都屬於 $s$ 的邊的集合，連通即滿足 $s$ 中的任意兩點可以被若干 $E_s$ 中的邊所連通。

你最初可以任選一個城市開始發展。假設你目前感染的城市點集是 $S$，下一步擴張的點集是 $T$（只需保證 $S \subset T$，且 $T$ 連通），那麼稱這一步的 DNA 點數消耗是 $(|T| − |S |)\times w(T)$。

請找到一條感染計畫，即一個點集序列 $S_1 \subset S_2 \subset... \subset S_k$，其中 $S_1$ 只包含一個城市，$S_k$ 包含所有城市，每一步都要保證集合是連通的，最小化擴張的總 DNA 點數消耗。

輸入格式

第一行兩個正整數 $n, m$，表示城市數量和道路數量。

接下來 $m$ 行，每行 3 個正整數 $u,v,w$，表示一條交通路線。

輸出格式

輸出一行一個正整數，為最小 DNA 代價。

範例

範例 1 輸入

3 3
1 2 1
2 3 2
1 3 3

範例 1 輸出

6

範例 2

見下發文件

範例 3

見下發文件

子任務

對於 100% 的資料，$1\le n \le 20, 1\le m \le 100,1\le w \le 10000$，保證圖連通。

子任務 1（20pts）：$n\le 3, m\le 10$

子任務 2（10pts）：$n\le 4, m\le 10$

子任務 3（10pts）：$n\le 5, m\le 10$

子任務 4（20pts）：$n\le 10, m\le 100$

子任務 5（20pts）：$n\le 16, m\le 100$

子任務 6（20pts）：$n\le 20, m\le 100$