Heros
Limit pamięci: 256 MB
Bajtyzeusz, najsłynniejszy bajtocki heros, kolejny raz zwycięsko wyszedł z bitwy.
Podczas gdy załoga jego statku ładuje na pokład zdobyte kosztowności,
Bajtyzeusz w swojej kajucie planuje drogę powrotną do rodzinnej Bitaki.
Nie jest to łatwe zadanie. Wielu bogów zazdrości Bajtyzeuszowi popularności
wśród bajtockiego ludu i chętnie utarłoby mu nosa.
Na szczęście, niektórzy z nich patrzą na niego przychylnie, a zwłaszcza bogini Bajtena.
I to ona właśnie zesłała wczoraj w nocy Bajtyzeuszowi sen, w którym ostrzegła
go o grożących mu niebezpieczeństwach.
Na Morzu Bajtockim znajduje się wysp, które wygodnie nam będzie ponumerować liczbami
od do . Aktualnie statek Bajtyzeusza znajduje się na wyspie , zaś celem podróży
jest Bitaka - wyspa .
Niektóre pary wysp połączone są jednokierunkowymi szlakami morskimi,
przy czym każda z wysp jest początkiem co najwyżej szlaków.
Szlaki numerujemy liczbami od do ;
-ty szlak prowadzi z wyspy na wyspę , a jego pokonanie wymaga dokładnie dni.
Jeśli więc statek wyruszy -tym szlakiem z wyspy początkowej o świcie dnia , to na wyspę docelową
dotrze o świcie dnia .
Na każdej z wysp statek może czekać dowolnie długo przed wyruszeniem w drogę.
Jednak zanim dotrze do kolejnej wyspy, nie może zboczyć z raz obranego szlaku ani płynąć dłużej niż wymaga tego szlak.
Z wyspy Bajtyzeusz może wyruszyć najwcześniej o świcie pierwszego dnia.
Ostrzeżenie Bajteny było bardzo konkretne.
Podała ona Bajtyzeuszowi dokładną listę
pułapek, które przygotowali bogowie. Każda z nich znajduje się na pewnej
wyspie i jest aktywna przez pewien przedział czasu. Konkretniej mówiąc, -ta pułapka
znajduje się na wyspie i jest aktywna cały czas od dnia do dnia włącznie.
Pułapki są naprawdę niebezpieczne - jeżeli statek Bajtyzeusza
znajdzie się na wyspie z aktywną pułapką, to żaden członek załogi nie ujdzie z życiem.
Szczęśliwie rodzinna Bitaka jest wolna od pułapek, a na wyspie żadna pułapka nie jest aktywna pierwszego dnia.
Oczywiste jest, że Bajtyzeusz chce tak zaplanować drogę do domu, aby ominąć wszystkie pułapki.
Zastanawia się jednak, jak bardzo wydłuży to czas podróży.
Pomóż mu i wyznacz minimalną liczbę dni potrzebnych na bezpieczny powrót do Bitaki.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite
i (, ),
oznaczające liczbę wysp i liczbę szlaków na morzu.
Kolejne wierszy opisuje szlaki: w -tym z nich
znajdują się trzy liczby całkowite
(, , ),
oznaczające, że -ty szlak prowadzi z wyspy na wyspę
i pokonanie go trwa dni.
Wszystkie szlaki są jednokierunkowe.
Na każdej wyspie zaczyna się co najwyżej szlaków.
Następny wiersz zawiera liczbę całkowitą
(), oznaczającą liczbę pułapek.
Kolejne wierszy opisuje pułapki: w -tym z nich
znajdują się trzy liczby całkowite
(, ),
oznaczające, że -ta pułapka znajduje się na wyspie
oraz jest aktywna od dnia do dnia włącznie.
Jeśli , to .
Wyjście
Jeśli nie można tak zaplanować drogi, by ominąć wszystkie pułapki,
w pierwszym i jedynym wierszu wyjścia należy wypisać słowo NIE.
W przeciwnym wypadku należy wypisać liczbę całkowitą , oznaczającą
minimalną liczbę dni potrzebnych na odbycie podróży (tzn. statek dociera
do Bitaki świtem dnia ).
Przykład
Dla danych wejściowych:
5 6
1 2 3
1 4 13
2 3 1
2 4 2
3 2 2
4 5 1
5
1 2 4
1 8 8
2 6 7
2 10 11
4 6 7
poprawną odpowiedzią jest:
10
Wyjaśnienie do przykładu:
Bajtyzeusz wyrusza z wyspy o świcie pierwszego dnia i dociera na wyspę czwartego dnia.
Tam czeka jeden dzień, a następnie wyrusza na wyspę 3 i po dotarciu
na nią szóstego dnia od razu zawraca na wyspę 2, skąd ósmego dnia wypływa w stronę wyspy 4.
Przybywa na nią dziesiątego dnia i ostatecznie jedenastego dnia dopływa do Bitaki.
Autor zadania: Tomasz Idziaszek