Koleje

Limit pamięci: 32 MB

Bajtockie Koleje Państwowe (BKP) stanęły przed koniecznością restrukturyzacji i redukcji sieci linii kolejowych. Po dokładnym przeanalizowaniu sieci linii kolejowych zdecydowano, które stacje kolejowe mają być zlikwidowane, a które mają pozostać. Zdecydowano się także maksymalnie zredukować sieć linii kolejowych. Trzeba jeszcze wybrać, które linie kolejowe mają być zlikwidowane, a które mają pozostać.

Sieć linii kolejowych składa się z odcinków torów łączących stacje kolejowe. Wiadomo, że z każdej stacji kolejowej da się dojechać do każdej innej stacji kolejowej (potencjalnie odwiedzając stacje pośrednie). Odcinki torów są dwukierunkowe. Między każdą parą stacji może być co najwyżej jeden odcinek torów. Każdy taki odcinek torów charakteryzuje się kosztem utrzymania, dodatnią liczbą całkowitą. Odcinki torów, które mają pozostać, muszą być tak wybrane aby:

• dało się przejechać między każdymi dwiema stacjami, które mają pozostać,
• ich sumaryczny koszt utrzymania był mały (może być co najwyżej dwukrotnie większy od najmniejszego kosztu, jaki da się uzyskać zachowując poprzedni warunek).

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis sieci linii kolejowych oraz stacje, które mają pozostać,
• wyznaczy, które odcinki torów mają pozostać, a które mają być zlikwidowane,
• wypisze na standardowe wyjście, które odcinki torów mają pozostać oraz poda ich sumaryczny koszt utrzymania.

Wejście

W pierwszym wierszu standardowego wejścia zapisane są dwie dodatnie liczby całkowite i , , (), oddzielone pojedynczym odstępem. Liczba to liczba stacji kolejowych, a - liczba odcinków torów. Stacje kolejowe są ponumerowane od do . W kolejnych wierszach są opisane odcinki torów kolejowych, po jednym w wierszu. W każdym z tych wierszy są zapisane po trzy dodatnie liczby całkowite , i , , , . Liczby i to numery stacji, które łączy dany odcinek torów, a to jego koszt utrzymania. W wierszu zapisany jest ciąg liczb całkowitych pooddzielanych pojedynczymi odstępami. Pierwsza z nich to - liczba stacji, które mają pozostać (, ). Dalej w tym wierszu wymienione są numery tych stacji w kolejności rosnącej.

Wyjście

W pierwszym wierszu standardowego wyjścia program powinien wypisać dwie liczby całkowite i oddzielone spacją, gdzie jest sumarycznym kosztem utrzymania pozostawionych odcinków, a - liczbą tych odcinków. W każdym z kolejnych wierszy powinny znaleźć się dwie liczby oraz , oddzielone spacją - numery stacji, które łączą pozostawione odcinki torów. Sumaryczny koszt utrzymania odcinków torów może być co najwyżej dwukrotnie większy od najmniejszego kosztu, możliwego do uzyskania.

Przykład

Dla danych wejściowych:

8 11
1 2 6
3 1 5
2 3 8
3 4 9
3 5 10
5 4 3
5 6 9
6 4 8
6 8 8
6 7 7
8 7 10
4 2 5 7 8

poprawną odpowiedzią jest:

42 5
2 3
3 5
5 6
6 7
6 8

Autor zadania: Marcin Kubica.