Problem description
Jasio jedzie samochodem przez Bajszawę, od swojego kolegi Bajtazara na halę mistrzostw świata w programowaniu zespołowym Bajto 2012. W Bajszawie jest N skrzyżowań i M jednokierunkowych dróg łączących te skrzyżowania. Drogi się nie przecinają, mogą jednak prowadzić tunelami lub estakadami. Skrzyżowania są jedynymi miejscami, na których można skręcać.
Niektóre z bajtockich przepisów są bezsensowne – w szczególności nikt nie pomyślał o właściwych kierunkach dróg, przez co może się zdarzyć, że przepisowa jazda pomiędzy bliskimi skrzyżowaniami może zająć bardzo dużo czasu lub być wręcz niemożliwa. Jasio próbując znaleźć kompromis między czasem dojazdu na halę Bajto 2012, a swoim czystym sumieniem postanowił, że jadąc niektórymi drogami pojedzie pod prąd – zrobi to jednak co najwyżej K razy. Czy zdąży na finałowe spotkanie drużyny Bajtocji z Bitocją? Napisz mu ten program, bo nie da Ci spokoju.
Napisz program, który: wczyta liczbę skrzyżowań, drogi między nimi oraz liczbę K, wyznaczy minimalny czas przejazdu na Bajto 2012 i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się trzy liczby naturalne N, M oraz K, pooddzielane pojedynczymi odstępami i oznaczające: liczbę skrzyżowań, liczbę dróg między nimi oraz maksymalną założoną przez Jasia liczbę razy, w których pojedzie przez drogę niezgodnie z jej zwrotem. W kolejnych M wierszach znajdują się opisy kolejnych dróg. Opis każdej drogi składa się z trzech liczb naturalnych u, v, c, pooddzielanych pojedynczymi odstępami i określających drogę ze skrzyżowania u do skrzyżowania v, którą Jasio (niezależnie od kierunku jazdy) pokona w czasie c. Możesz założyć, że dom Bajtazara jest przy skrzyżowaniu numer 1, a hala Bajto 2012 przy skrzyżowaniu numer N.
Wyjście
W pierwszym i jedynym wierszu wyjścia należy wypisać minimalny
możliwy czas przejazdu na Bajto 2012. Jeżeli przejazd jest niemożliwy
należy wypisać na wyjście NIE.
Ograniczenia
2 ≤ N ≤ 10 000, 0 ≤ M ≤ 30 000, 0 ≤ K ≤ 50, dla każdej drogi: 1 ≤ c ≤ 100 000.
Przykład
| Input | Output | |
|
|