Dookoła świata [A]

Limit pamięci: 128 MB

Jacek chce oblecieć świat dookoła. Niestety nie ma zbyt wielu pieniędzy, wobec czego chce to zrobić jak najtaniej. Jacek zorientował się, że stosunkowo tanie są loty Bajtolinii Lotniczych, dlatego sprawdził wszystkie połączenia w ich ofercie. Siedzi teraz nad mapą i kombinuje. Pomóż mu!

Dane Jacka to lista miast oraz lista połączeń między tymi miastami. Dla każdego z miast Jacek zna jego długość geograficzną. Każdy z lotów łączy dwa miasta i umożliwia podróż w obydwóch kierunkach - jeśli z miasta do miasta możemy dolecieć za bajtalarów, to podróż z miasta do miasta również jest możliwa i kosztuje bajtalarów.

Dla każdego połączenia wiemy, czy samoloty wykonujące to połączenie lecą na zachód, czy też na wschód (zakładamy, że żadne dwa miasta nie mają tej samej długości geograficznej). Każdy samolot leci cały czas wprost do celu, a trasa żadnego lotu nie prowadzi nad biegunem i nie okrąża Ziemi w pełni (tj. samolot przebywa mniej niż długości geograficznej).

Powstał jeszcze jeden problem. Co to znaczy "oblecieć świat dookoła"? Jacek ustalił, że chce, aby podczas całej podróży łączna liczba stopni długości geograficznej przebytych na wschód była różna od liczby stopni przebytych w kierunku zachodnim. Jacek planuje rozpocząć i zakończyć podróż w swoim rodzinnym mieście.

Rozważmy następujące przykłady (zakładamy w nich, że wszystkie loty są w rozsądnym kierunku, tj. w tym, w którym przelatujemy mniej niż 180 stopni):

• lot Warszawa (E) - Moskwa (E) - Tokio (E) - Los Angeles (W) - Nowy Jork (W) - Warszawa (E) jest lotem dookoła świata (w trakcie całej podróży lecimy na wschód);
• lot Warszawa (E) - Moskwa (E) - Tokio (E) - Los Angeles (W) - Miami (W) - Kair (E) - Dublin (W) - Warszawa (E) też jest lotem dookoła świata (na wschód lecimy ponad , zaś na zachód jedynie w trakcie lotu z Kairu do Dublina);
• lot Warszawa (E) - Moskwa (E) - Singapur (E) - Los Angeles (W) - Miami (W) - Kair (E) - Delhi (E) - Sydney (E) - Buenos Aires (W) - Johannesburg (E) - Warszawa (E) jest lotem dookoła świata (na wschód przebywamy ponad , zaś na zachód jedynie kilka stopni w trakcie lotu z Johannesburga do Warszawy);
• lot Warszawa (E) - Moskwa (E) - Singapur (E) - Los Angeles (W) - Miami (W) - Kair (E) - Johannesburg (E) - Buenos Aires (W) - Sydney (E) - Delhi (E) - Kijów (E) - Warszawa (E) nie jest lotem dookoła świata (liczba stopni przebytych w kierunku wschodnim jest dokładnie taka sama, jak liczba stopni przelecianych na zachód).

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i () oznaczające odpowiednio liczbę miast na mapie Jacka oraz liczbę lotów dostępnych w Bajtoliniach Lotniczych. Miasta są ponumerowane liczbami od do . Jacek rozpoczyna podróż w mieście numer . W drugim wierszu znajdują się współrzędne kolejnych miast podane jako ciąg liczb całkowitych (). Liczba oznacza, ile sekund geograficznych na wschód od południka zerowego leży miasto numer ( sekunda to stopnia). Żadne dwa miasta nie mają tej samej długości geograficznej.

Każdy z kolejnych wierszy opisuje jeden lot. W -tym z tych wierszy znajdują się cztery liczby całkowite (, , , ). Oznaczają one, że Bajtolinie oferują przeloty pomiędzy miastami numer oraz w cenie bajtalarów i trasa lotu z miasta do miasta prowadzi na wschód (gdy ) lub na zachód (gdy ). Trasa lotu powrotnego prowadzi w przeciwnym kierunku.

Wyjście

Twój program powinien wypisać na wyjście koszt (w bajtalarach) najtańszej podróży dookoła świata, która rozpoczyna się i kończy się w mieście numer . Jeśli takiej podróży nie ma, program powinien wypisać .

Przykład

Dla danych wejściowych:

5 7
75630 135420 502890 1029600 870750
4 3 1 1
3 2 4 -1
3 5 7 1
1 5 15 1
1 4 10 -1
1 2 2 1
5 4 3 1

poprawną odpowiedzią jest:

23

Autor zadania: Jakub Wojtaszczyk.