Tramwaje
Limit pamięci: 128 MB
Z powodu nieustannych podwyżek cen prądu, burmistrz Bajtocji został zmuszony do
ostrych cięć budżetowych, skutkiem czego od niedawna bajtockie tramwaje nie wyjeżdżają w trasy.
Oczywiście wpływa to bardzo niekorzystnie na sytuację komunikacyjną w mieście, gdyż
wszyscy mieszkańcy muszą się teraz kisić w zatłoczonych autobusach.
Jednak jest promyk nadziei: Bajtocja ma szansę na dotację z Ministerstwa Infrastruktury Bitowej.
W tym celu musi złożyć stosowny wniosek, w którego przygotowaniu bierzesz udział.
Sieć tramwajowa w Bajtocji składa się z skrzyżowań i odcinków torów; z każdego
skrzyżowania można dojechać torami do dowolnego innego. Przy każdym skrzyżowaniu, do którego
dochodzi tylko jeden odcinek torów, znajduje się pętla tramwajowa.
Oznaczmy liczbę pętli przez .
Miasto posiada tramwajów, każdy z nich ma jeździć po swojej trasie,
która łączy dwie różne pętle tramwajowe i nie przechodzi dwa razy przez to samo skrzyżowanie.
Trasy odpowiadające różnym tramwajom mogą przechodzić przez to samo skrzyżowanie lub odcinek
torów, ale na danej pętli tramwajowej może zaczynać się lub kończyć co najwyżej jedna trasa.
Koszt prądu, który zużywa dziennie tramwaj, jest proporcjonalny do długości jego trasy.
Zatem sumaryczny koszt dotacji, o którą ubiega się burmistrz, w istotny sposób zależy
od ustalenia planu tras dla tramwajów.
Burmistrz jest zainteresowany minimalnym i maksymalnym kosztem, które można uzyskać
rozważając poprawne plany tras. Twoim zadaniem jest wyznaczyć te dwie liczby.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita ()
oznaczająca liczbę skrzyżowań w sieci tramwajowej. Skrzyżowania są ponumerowane liczbami od 1 do .
W -tym z kolejnych wierszy znajdują się po trzy liczby całkowite , ,
(, , )
oznaczające numery skrzyżowań, które łączy -ty odcinek torów, oraz długość tego odcinka.
Wyjście
Na wyjściu należy wypisać dokładnie dwa wiersze.
W pierwszym z nich powinna się znaleźć minimalna sumaryczna długość tras tramwajowych,
którą da się uzyskać dla jakiegoś poprawnego planu.
W drugim wierszu należy wypisać maksymalną sumaryczną długość tras.
Ocenianie
Jeśli Twój program poprawnie wyznacza dokładnie jedną z liczb na wyjściu, dostaniesz
połowę liczby punktów za test.
Przykład
Dla danych wejściowych:
8
1 3 1
2 3 1
3 4 1
4 5 1
5 6 1
5 7 2
5 8 1
poprawną odpowiedzią jest:
4
9
Autor zadania: Tomasz Idziaszek, Tomasz Kociumaka.