Runda 4: Wielka Teoria Wszystkiego

24.06.2009

Matematyka jest jak wielkie, rozłożyste drzewo: ma korzenie, pień, grube gałęzie, konary, wreszcie cieńkie gałęzie i niepozorne listeczki. Listeczków tych jest wiele, tak wiele, że nikt nie może się w tym do końca połapać. Dlatego matematycy poświęcają swe życia, aby opiekować się tym wielkim drzewem. Każdy siedzi na swojej gałęzi i obcina listeczki, albo przynajmniej stara sie kontrolować ich ilość.

Jednak Ty jesteś matematykiem innowacyjnym - matematykiem XXI wieku. Postanowiłeś opracować Wielką Teorię Wszystkiego, która zastąpi dotychczasowe teorie, będzie prosta, piękna, uniwersalna i obejmie całą matematykę. Pierwszym krokiem twego planu jest dokonanie Wielkiej Unifikacji - mianowicie chcesz udowodnić, że wszystkie teorie z pewnego zbioru są równoważne. Oczywiście nie musisz udowadniać równoważności każdej pary teorii, jako doskonały matematyk dobrze wiesz, że jeżeil A jest równoważne B, a B jest równoważne C, to A jest równoważne C.

Oszacowałeś ilość pracy wymaganej, aby udowodnić równoważność niektórych teorii. Ponieważ jesteś leniwym matematykiem, zastanawiasz się, jaka jest minimalna ilość pracy wymagana, aby udowodnić równoważność wszystkich teorii w zbiorze.

Wejście

W pierwszej linii wejścia dane są dwie liczby n, m (1 ≤ n ≤ 7 000, 1 ≤ m ≤ 1 000 000), oznaczające odpowiednio ilość teorii w zbiorze oraz ilość par, dla których oszacowałeś koszt udowodnienia równoważności. Następnie danych jest m lini, z których każda zawiera trzy liczby a, b, c (1 ≤ a, bn, 1 ≤ c ≤ 1 000) oznaczające, że koszt udowodnienia równoważności teorii a oraz b wynosi c.

Wyjście

Na wyjściu należy wypisać jedną liczbę całkowitą - minimalny koszt udowodnienia równoważności wszystkich teorii w zbiorze.

Przykład

Dla danych wejściowych

6 12
4 5 5
2 5 21
3 5 29
5 6 7
2 6 4
4 6 5
3 4 16
2 4 2
3 6 1
1 3 12
1 6 29
2 3 2

poprawną odpowiedzią jest

22

kod: LAZYMATH, limity: 6 s, 32 MB

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com