Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

XIWTPZD - Ulotki

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

Wejście

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

Wyjście

22
320

Dodane przez:Michael Suchacz
Data dodania:2010-04-02
Limit czasu wykonania programu:0.100s-0.686s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU NODEJS OBJC PERL6 SQLITE VB.NET
Pochodzenie:XI Wiosenny Turniej w Programowaniu Zespołowym
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.