Archiwum zadań programistycznych WWSI

Pamiętasz Marka z Politechniki Marsjańskiej? Nie przejmuj się, on Ciebie też nie. Od czasu kiedy częściowo naprawił swój zegarek i przestał się spóźniać jego życie stało się zdecydowanie przyjemniejsze. Nasz znajomy skończył studia i nawet dostał dobrze płatną pracę przy organizacji Euro 4024.

Nazwa to pozostałość po zawodach rozgrywanych dawno temu. Niestety nikt nie wie o co właściwie w nich chodziło. Obecnie Euro to ogromna impreza przyciągająca masę ludzi. Przez dobę ponad 100 zawodników rywalizuje grając w wojnę. Emocje sięgają zenitu ;-) Impreza ta zazwyczaj odbywa się na kilku planetach, dlatego też kibice muszą mieć zapewniony odpowiedni transport. Niestety statki kosmiczne, które będą przewozić kibiców na Euro 4024 są w opłakanym stanie. Na dodatek są to starsze, potwornie wolne modele, lot z jednaj planety na drugą trwa czasami nawet kilka minut. Wszystko to powoduje, że kibice nie dolatują na czas, a kolejki oczekujących na wylot są ogromne. Nie pomaga nawet fakt, że pomiędzy niektórymi parami planet uruchomiono kilka linii.

Organizatorzy mają tego dość, postanowili zmodernizować część linii przed rozpoczęciem imprezy, a resztę po prostu zamknąć. Chcą oni jednak aby koszt inwestycji był jak najmniejszy i aby nadal był możliwy przelot pomiędzy każdą parą planet (może być z przesiadkami). Po tych ustaleniach zapuścili funkcję rand() no i wypadło, że to Marek obliczy koszt inwestycji. To ile to będzie?

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite p oraz l (1 ≤ p ≤ 700, 1 ≤ l ≤ 500000) określające odpowiednio ilość planet, na których rozgrywane będzie Euro 4024 i ilość obecnie działających linii komunikacji międzyplanetarnej. W kolejnych l wierszach znajdują się opisy tych linii.

Opis każdej linii zawarty jest w osobnym wierszu. Zawiera on trzy liczby naturalne a, b oraz k (0 ≤ a, b ≤ p-1, 1 ≤ k ≤ 10000). Liczby a i b to numery planet pomiędzy, którymi kursują statki danej linii, zaś k to koszt jej ewentualnej modernizacji.

Wyjście

W pierwszej i jedynej linii wyjścia należy wypisać szukany koszt inwestycji.

Przykład

Wejście:

4 6
0 1 100
0 1 18
1 2 40
0 2 70
2 3 2
3 2 11

Wyjście:

60