Modernizacja autostrady
Limit pamięci: 64 MB
Król Bajtocji wydał niedawno dekret o modernizacji części autostrad. Inżynierowie królestwa
obliczyli koszt modernizacji każdej autostrady. Znane są również długości wszystkich autostrad. Każda autostrada jest
dwukierunkowa i łączy dwa miasta. Pozostaje problem wyboru, które autostrady modernizować. Główny Inżynier
zwrócił się z tym pytaniem do króla. Król pomyślał chwilę i przedstawił swoje wymagania:
- Musi dać się dojechać zmodernizowanymi autostradami ze stolicy do miasta, gdzie odbywać się będą najbliższe międzynarodowe targi.
- Średni koszt modernizacji kilometra autostrady musi być najmniejszy możliwy.
Napisz program, który wybierze autostrady tak, aby średni koszt modernizacji wybranych autostrad na kilometr był możliwie
najmniejszy, i wypisze ten koszt na standardowe wyjście.
Wejście
W pierwszym wierszu znajdują się dwie liczby całkowite oddzielone pojedynczym odstępem, liczba miast i
liczba autostrad ().
Miasta ponumerowane są od 1 do . Stolica ma
numer 1, targi odbywają się w mieście numer 2.
Każdy z kolejnych wierszy zawiera opis jednej autostrady w
postaci czterech liczb oddzielonych odstępami , , ,
(). Opisują
one autostrady łączące miasta i , z kosztem modernizacji bajtodolarów i o długości .
Wyjście
Jeśli nie da się spełnić warunków króla, należy w jedynym wierszu wypisać jedno słowo NIE. W przeciwnym
razie należy wypisać minimalny średni koszt modernizacji kilometra autostrady w optymalnym rozwiązaniu.
Innymi słowy, jest to suma kosztów modernizacji wybranych autostrad podzielona na sumę długości wybranych autostrad.
Wynik należy wypisać w postaci ułamka w najprostszej postaci (nieskracalnego), czyli dwóch liczb całkowitych
oddzielonych znakiem dzielenia (liczby całkowite wypisujemy w postaci ).
Przykład
Dla danych wejściowych:
3 3
2 1 10 3
2 1 15 10
2 3 1 4
poprawną odpowiedzią jest:
8/7
Autor zadania: Tomasz Czajka (odgrzewane).