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