The world is a connected graph consisting of $n$ cities and $m$ transportation routes. Each transportation route has a weight. The weight of a connected subgraph $w(s)$ is defined as the XOR sum of the weight of its minimum spanning tree and the weight of its maximum spanning tree.
Note:
- $w(s)$ is only defined for connected subgraphs $(s, E_s)$ of the graph $G$.
- For a connected subgraph $(s, E_s)$, where $s$ is the set of vertices and $E_s = \{(u, v) \in E \mid u, v \in s\}$ is the set of all edges whose endpoints both belong to $s$, "connected" means that any two vertices in $s$ can be connected by a sequence of edges in $E_s$.
You can initially choose one city to start developing. Suppose the set of cities you have currently infected is $S$, and the set of cities you expand to in the next step is $T$ (ensuring $S \subset T$ and $T$ is connected). Then, the DNA point consumption for this step is $(|T| - |S|) \times w(T)$.
Find an infection plan, which is a sequence of vertex sets $S_1 \subset S_2 \subset \dots \subset S_k$, where $S_1$ contains only one city, $S_k$ contains all cities, and each step ensures the set is connected, such that the total DNA point consumption is minimized.
Input
The first line contains two positive integers $n$ and $m$, representing the number of cities and the number of roads.
The next $m$ lines each contain three positive integers $u, v, w$, representing a transportation route.
Output
Output a single positive integer, which is the minimum DNA cost.
Examples
Input 1
3 3 1 2 1 2 3 2 1 3 3
Output 1
6
Input 2
See provided files.
Output 2
See provided files.
Input 3
See provided files.
Output 3
See provided files.
Subtasks
For 100% of the data, $1 \le n \le 20$, $1 \le m \le 100$, $1 \le w \le 10000$. The graph is guaranteed to be connected.
Subtask 1 (20pts): $n \le 3, m \le 10$
Subtask 2 (10pts): $n \le 4, m \le 10$
Subtask 3 (10pts): $n \le 5, m \le 10$
Subtask 4 (20pts): $n \le 10, m \le 100$
Subtask 5 (20pts): $n \le 16, m \le 100$
Subtask 6 (20pts): $n \le 20, m \le 100$