XI Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 26 V 2007

Opis

Denerwują Cię ludzie, którzy na przystankach autobusowych wręczają Ci setki głupich ulotek? Mnie też. Too bad, bo Twoim zadaniem jest napisanie programu, który pomoże firmie, dla której pracują...

W pewnym mieście zatrudniono studentów do rozdawania ulotek. Każdemu z nich został przypisany dokładnie jeden przystanek autobusowy, na którym spędza on cały dzień, rozdając ulotki spotkanym tam ludziom.

System transportowy w tym mieście jest dość specyficzny. Linie autobusowe są jednokierunkowe i każda łączy dokładnie dwa przystanki, autobusy nie zatrzymują się pomiędzy przystankami. Opłata za przejazd daną linią (tj. pomiędzy dwoma przystankami) jest określona w specjalnych tablicach. Połączenia autobusowe są rozplanowane w ten sposób, że każda trasa w dwie strony (tj. trasa, która zaczyna się i kończy na tym samym przystanku) musi przebiegać przez dworzec centralny.

Zatrudnieni studenci każdego ranka wyruszają z dworca centralnego. Każdy z nich musi dotrzeć do przydzielonego mu przystanku autobusowego. Każdy student ma przydzielony dokładnie jeden przystanek i każdy przystanek ma przydzielonego dokładnie jednego studenta. Wieczorem studenci muszą wrócić na dworzec centralny.

Twoim zadaniem jest napisanie programu, który pomoże zminimalizować sumaryczny koszt przejazdów, który firma ponosi każdego dnia, opłacając przejazdy zatrudnionych studentów.

Specyfikacja wejścia

Pierwsza linia wejścia zawiera pojedynczą liczbę, oznaczającą liczbę testów. W kolejnych liniach opisane są kolejne testy. Każdy test rozpoczyna się linią zawierającą dwie liczby całkowite A i B, (1 ≤ A,B ≤ 1000000). A jest liczbą przystanków autobusowych (licząc również dworzec centralny), a B jest liczbą linii autobusowych. W każdej z kolejnych B linii znajduje się opis jednej linii autobusowej. Linia składa się z trzech liczb - numeru przystanku początkowego, numeru przystanku docelowego i ceny biletu. Dworzec centralny ma numer 1. Ceny są dodatnimi liczbami całkowitymi. Ich suma nie przekracza 1000000000. Możesz założyć, że z każdego przystanku można dotrzeć do każdego innego.

Specyfikacja wejścia

Dla każdego testu, wypisz jedną linię, zawierającą minimalną kwotę pieniędzy potrzebną każdego dnia na przejazdy zatrudnionych studentów.

Przykład

2
2 2
1 2 5
2 1 17
5 7
2 1 65
5 1 30
1 2 20
3 4 10
1 3 20
2 4 10
4 5 20

22
320