W pewnej firmie komputery połączone są w sieć w celu przesyłania danych. Każdy komputer połączony jest bezpośrednio z pewną liczbą innych komputerów. Komputery połączone są w taki sposób, aby istniała możliwość przesłania danych z dowolnego komputera do innego komputera w sieci. Aby dane mogły zostać przesłane pomiędzy dwoma komputerami nie muszą one być połączone ze sobą bezpośrednio, gdyż przesyłanie danych może się odbyć poprzez inny komputer. Firma postanowiła zmodernizować sieć całkowicie wymieniając okablowanie. Ponieważ chce na to zużyć jak najmniejszą ilość kabla, dlatego postanowiono usunąć z sieci zbędne połączenia. Po usunięciu zbędnych połączeń powinna w dalszym ciągu być możliwość przesyłania danych z dowolnego komputera do pozostałych komputerów w sieci.
Twoim zadaniem jest napisanie programu, który dla zadanego opisu sieci komputerowej wyznaczy ile maksymalnie kabla można zaoszczędzić usuwając zbędne połączenia w sieci.
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita będąca liczbą zestawów danych. W kolejnych wierszach znajdują się kolejne zestawy danych.
Opis jednego zestawu danych składa się z m + 1 wierszy, gdzie w pierwszym wierszu znajdują się dwie liczby całkowite n, m oddzielone pojedynczym odstępem oznaczające odpowiednio: n (1 ≤ n ≤ 1650) - liczbę komputerów w sieci; m (0 ≤ m ≤ n*(n-1)/2) - liczbę wszystkich połączeń między komputerami. Kolejnych m wierszy zawiera trzy liczby całkowite: x (1 ≤ x ≤ n), y (1 ≤ y ≤ n), d (1 ≤ d ≤ 100) oddzielone pojedynczym odstępem, gdzie x, y określają numery komputerów jakie są ze sobą połączone, natomiast d - ilość kabla jakim są połączone.
W kolejnych wierszach wyjścia powinny znaleźć się dwie liczby całkowite a, b oddzielone pojedynczym odstępem określające odpowiednio: a - maksymalną liczbę połączeń jakie mogą być usunięte z sieci, b - maksymalną ilość kabla jaka może być zaoszczędzona przez usunięcie zbędnych połączeń.
4 3 3 1 2 15 2 3 23 3 1 14 5 7 1 2 18 1 4 22 1 5 25 2 3 31 2 4 11 4 3 9 5 4 17 5 4 1 2 10 2 3 12 3 4 8 4 5 11 5 4 1 2 5 1 3 9 1 4 12 1 5 24
1 23 3 78 0 0 0 0