Cennik

Limit pamięci: 64 MB

Najpopularniejszym środkiem transportu w Bajtocji od zawsze była kolej. Spośród miast tego kraju, par miast jest połączonych odcinkami torów należącymi do Bajtockich Kolei Państwowych (BKP). Odcinki nie krzyżują się nigdzie poza miastami i mogą prowadzić tunelami lub mostami. Koszt przejazdu między dwoma miastami połączonymi bezpośrednio odcinkiem torów jest zawsze taki sam i wynosi bajtalarów.

Obecnie sytuacja na rynku usług komunikacyjnych w Bajtocji uległa zmianie. Pojawiła się konkurencja dla BKP - powstały Bajtockie Linie Lotnicze (BLL). BLL zamierzają uruchomić połączenia lotnicze między niektórymi parami miast. Ponieważ jazda bajtocką koleją jest bardzo wygodna, zarząd BLL postanowił uruchamiać połączenia lotnicze tylko między takimi parami miast, dla których nie istnieje bezpośrednie połączenie kolejowe. Ze względów ekonomicznych, BLL utworzy połączenia lotnicze jedynie między tymi parami miast, dla których najtańsze połączenie kolejowe wymaga dokładnie jednej przesiadki. Koszt biletu lotniczego na jedno połączenie będzie stały i równy bajtalarów.

Żeby pomóc mieszkańcom Bajtocji w planowaniu podróży, Ministerstwo Transportu Bajtocji (MTB) postanowiło stworzyć cenniki zawierające koszty najtańszych tras między poszczególnymi miastami kraju. Trasę rozumiemy tu jako sekwencję złożoną z dowolnej liczby pojedynczych połączeń kolejowych lub lotniczych. Zadanie stworzenia cenników przypadło w udziale Bajtazarowi, który pracuje jako urzędnik w MTB. Czy pomógłbyś mu w napisaniu programu, który wyznaczy odpowiednie cenniki?

Dodajmy dla jasności, że wszystkie połączenia kolejowe i lotnicze w Bajtocji są dwukierunkowe.

Wejście

Pierwszy wiersz standardowego wejścia zawiera pięć liczb całkowitych , , , oraz (, , , ) pooddzielanych pojedynczymi odstępami. Liczby oraz oznaczają odpowiednio liczbę miast oraz liczbę połączeń kolejowych w Bajtocji. Dla uproszczenia miasta w Bajtocji numerujemy od do . Kolejne liczby w wierszu oznaczają: - numer miasta początkowego, dla którego należy wygenerować cennik opisujący najtańsze trasy; - koszt biletu na jedno połączenie kolejowe; - koszt biletu na jedno połączenie lotnicze.

Każdy z kolejnych wierszy zawiera dwie liczby całkowite oraz (, dla ) oddzielone pojedynczym odstępem, oznaczające numery miast połączonych bezpośrednim odcinkiem torów.

Możesz założyć, że z miasta numer można dojechać koleją do wszystkich pozostałych miast kraju.

W testach wartych łącznie 30% punktów zachodzą dodatkowe warunki oraz .

Wyjście

Twój program powinien wypisać na standardowe wyjście wierszy. Wiersz o numerze (dla ) powinien zawierać jedną liczbę całkowitą: koszt najtańszej trasy z miasta numer do miasta numer . Spośród tych wierszy, wiersz o numerze powinien zawierać liczbę 0.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

0
3
3
2
5

Wyjaśnienie do przykładu: Najtańsza trasa z miasta numer 1 do miasta numer 5 wiedzie przez miasto numer 3 lub miasto numer 4. W obu przypadkach składa się ona z jednego połączenia kolejowego i jednego lotniczego.

Autor zadania: Jakub Radoszewski.