Wyprawa

Limit pamięci: 32 MB

W Bajtocji jest miast (ponumerowanych liczbami od do ). Miasta są połączone dwukierunkowymi drogami. Ponieważ król Bajtocji nie jest zbyt skory do inwestycji w rozbudowę dróg, jest ich zaledwie . Można jednak przy ich pomocy dotrzeć z dowolnego miasta do dowolnego innego miasta.

Pewnego dnia, podróżnik Bajtazar zawitał do miasta o numerze . Zamierza on odwiedzić jeszcze miasta , , ..., (niekoniecznie w tej kolejności) - liczby są parami różne i wszystkie są różne od . Bajtazarowi powoli kończą się fundusze przeznaczone na podróż, dlatego chciałby objechać wszystkie zaplanowane miasta za pomocą możliwie najkrótszej trasy (zaczynającej się w mieście ). Przez trasę rozumiemy ciąg jednej lub więcej dróg, w którym początek następnej drogi jest końcem poprzedniej. Pomóż Bajtazarowi wyznaczyć długość najkrótszej trasy odwiedzającej wybrane przez niego miasta.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia:
  • opis bajtockiej sieci dróg,
  • numer miasta, w którym znajduje się Bajtazar,
  • listę miast, które Bajtazar chciałby odwiedzić
• wyznaczy minimalną długość trasy Bajtazara
• wypisze wynik na standardowe wyjście

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite i oddzielone pojedynczym odstępem (, ), gdzie jest liczbą miast w Bajtocji, a - numerem miasta, w którym znajduje się Bajtazar.

Każdy z kolejnych wierszy opisuje jedną z dróg Bajtocji. Wiersz -szy (dla ) zawiera trzy liczby całkowite , i oddzielone pojedynczymi odstępami (, ), i są miastami połączonymi drogą, a jest długością drogi. Wiersz -szy zawiera pojedynczą liczbę całkowitą - liczbę miast, które Bajtazar chciałby odwiedzić (). Kolejny wiersz zawiera różnych liczb całkowitych oddzielonych pojedynczymi odstępami - są to numery miast wybranych przez Bajtazara (, ).

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać pojedynczą liczbę całkowitą - długość najkrótszej trasy Bajtazara.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

5

Autor zadania: Jakub Radoszewski.