Patrząc na motyle, które nie mogą przelecieć przez kraniec świata, kto ma prawo nie rozumieć?

Nieskierowany graf wraz z dwoma zbiorami wierzchołków $L$ oraz $R$ nazywamy grafem motylim wtedy i tylko wtedy, gdy spełnione są następujące warunki:

• $L \cup R$ stanowi cały zbiór wierzchołków grafu.
• $L \cap R$ jest niepusty.
• Dowolne dwa wierzchołki w $L$ można połączyć ścieżką przechodzącą wyłącznie przez wierzchołki należące do $L$.
• Dowolne dwa wierzchołki w $R$ można połączyć ścieżką przechodzącą wyłącznie przez wierzchołki należące do $R$.

Mając dany graf motyli z wagami krawędzi, znajdź podzbiór krawędzi o minimalnej sumie wag taki, aby po jego pozostawieniu graf nadal był grafem motylim.

Wejście

W pierwszej linii znajdują się cztery liczby całkowite dodatnie $n, m, l, r$, oznaczające odpowiednio liczbę wierzchołków, liczbę krawędzi oraz rozmiary zbiorów $L$ i $R$.

W kolejnych $m$ liniach znajdują się trzy liczby całkowite dodatnie $u, v, w$, opisujące krawędź między wierzchołkami $u$ i $v$ o wadze $w$.

W kolejnej linii znajduje się $l$ liczb całkowitych dodatnich oznaczających wierzchołki należące do zbioru $L$.

W kolejnej linii znajduje się $r$ liczb całkowitych dodatnich oznaczających wierzchołki należące do zbioru $R$.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą minimalną sumę wag krawędzi.

Przykład

Przykład 1

Wejście

4 5 3 3
1 2 1
2 3 2
3 4 3
4 1 4
1 3 5
1 2 3
1 4 3

Wyjście

9

Przykład 2

Wejście

4 5 3 3
1 2 1
2 3 2
3 4 3
4 1 4
1 3 10
1 2 3
1 4 3

Wyjście

10

Podzadania

Dla $100\%$ danych wejściowych zachodzą warunki: $1 \le n \le 10^5$; $n - 1 \le m \le 2 \times 10^5$; $1 \le l + r - n \le 11$; $1 \le u, v \le n$; $1 \le w \le 10^9$, a dany graf wraz ze zbiorami $L$ i $R$ tworzy graf motyli.

Dla $50\%$ danych wejściowych gwarantowane jest $n = 100$, natomiast dla pozostałych $50\%$ danych gwarantowane jest $n = 10^5$.

Każda z tych grup zawiera 10 zestawów testowych, w których wartości $l + r - n$ wynoszą odpowiednio $1, 3, 4, 5, 6, 7, 8, 9, 10, 11$.