Świat jest spójnym grafem składającym się z $n$ miast i $m$ tras komunikacyjnych. Każda trasa ma przypisaną wagę. Wartość $w(s)$ spójnego podgrafu definiuje się jako wynik operacji XOR sumy wag minimalnego drzewa rozpinającego (MST) oraz sumy wag maksymalnego drzewa rozpinającego tego podgrafu.
Uwaga:
- $w(s)$ jest zdefiniowane tylko dla spójnych podgrafów $(s, E_s)$ grafu $G$;
- W spójnym podgrafie $(s, E_s)$, gdzie $s$ jest zbiorem wierzchołków, a $E_s = \{(u,v) \in E \mid u, v \in s\}$ jest zbiorem wszystkich krawędzi, których oba końce należą do $s$, spójność oznacza, że dowolne dwa wierzchołki w $s$ można połączyć ścieżką złożoną z krawędzi należących do $E_s$.
Początkowo możesz wybrać jedno miasto, od którego rozpoczniesz rozwój. Załóżmy, że aktualny zbiór zainfekowanych miast to $S$, a zbiór miast po kolejnym kroku ekspansji to $T$ (przy założeniu, że $S \subset T$ oraz $T$ jest spójne). Wówczas koszt punktów DNA w tym kroku wynosi $(|T| - |S|) \times w(T)$.
Znajdź plan infekcji, czyli ciąg zbiorów $S_1 \subset S_2 \subset \dots \subset S_k$, gdzie $S_1$ zawiera tylko jedno miasto, $S_k$ zawiera wszystkie miasta, a każdy zbiór w ciągu jest spójny, tak aby zminimalizować całkowity koszt punktów DNA.
Wejście
W pierwszej linii znajdują się dwie liczby całkowite $n$ oraz $m$, oznaczające odpowiednio liczbę miast i liczbę dróg.
W kolejnych $m$ liniach znajdują się po 3 liczby całkowite $u, v, w$, opisujące trasę komunikacyjną.
Wyjście
Wypisz jedną liczbę całkowitą, oznaczającą minimalny koszt DNA.
Przykład
Przykład 1
Wejście
3 3 1 2 1 2 3 2 1 3 3
Wyjście
6
Przykład 2
Patrz załączone pliki.
Przykład 3
Patrz załączone pliki.
Podzadania
Dla 100% danych wejściowych: $1 \le n \le 20$, $1 \le m \le 100$, $1 \le w \le 10000$, graf jest spójny.
- Podzadanie 1 (20 pkt): $n \le 3, m \le 10$
- Podzadanie 2 (10 pkt): $n \le 4, m \le 10$
- Podzadanie 3 (10 pkt): $n \le 5, m \le 10$
- Podzadanie 4 (20 pkt): $n \le 10, m \le 100$
- Podzadanie 5 (20 pkt): $n \le 16, m \le 100$
- Podzadanie 6 (20 pkt): $n \le 20, m \le 100$