시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

Drogi w Dalekim Kraju są w bardzo złym stanie, ale pozwalają na dotarcie z każdego miasta do dowolnego innego (choć może to wymagać odwiedzenia wielu miast). Żeby temu zaradzić rząd Dalekiego Kraju postanowił wybudować autostrady. Z braku pieniedzy zdecydowano się na budowę najmniejszej możliwej liczby autostrad, które umożliwią przejazd pomiędzy dwoma dowolnymi miastami. Autostrady mają być zbudowane w miejsce istniejących (wybranych) dróg. Znany jest koszt przebudowy każdej drogi. Okazało się, że koszty przebudowy różnych dróg są różne. Autostrady mają zbudować prywatne przedsiębiorstwa za pieniądze publiczne. Rząd wie, że opinię społeczną nie tyle interesuje łączny koszt wybudowania wszystkich autostrad, ale to ile zarobią poszczególne przedsiebiorstwa. Dlatego zdecydowano się na wybudowanie takiej sieci autostrad, żeby koszt najdroższej z nich był jak najmniejszy. Jaki jest koszt budowy najdroższej autostrady przy takim założeniu? Wszystkie drogi i autostrady są dwukierunkowe.

Napisz program, który:

  • wczyta ze standardowego wejścia opis systemu drogowego w Dalekim Kraju i koszty przebudowy poszczególnych dróg na autostrady,
  • obliczy koszt budowy najdroższej autostrady przy założeniu, że wybuduje się ich jak najmniej, zapewniając jednocześnie przejazd autostradami pomiędzy dowolnymi dwoma miastami oraz że koszt budowy najdroższej z nich będzie jak najmniejszy,
  • wypisze wynik na standardowe wyjście.

입력

W pierwszym wierszu podane są dwie liczby całkowite n, m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000), oddzielone pojedynczym odstępem. Liczba n jest liczbą miast w Dalekim Kraju. Miasta są ponumerowane od 1 do n. Liczba m jest liczbą dróg. Każda droga łączy bezpośrednio dwa miasta. Każdy z następnych m wierszy zawiera trzy liczby całkowite opisujące jedną drogę wraz z kosztem jej przebudowy. Liczby oddzielone są pojedynczymi znakami odstępu. Dwie pierwsze liczby są numerami miast, które ta droga łączy, natomiast trzecia liczba jest kosztem przebudowy drogi na autostradę. Koszt pojedyczej przebudowy jest dodatnią liczbą całkowitą nie większą niż 1 000 000.

출력

Pierwszy i jedyny wiersz powinien zawierać koszt budowy najdroższej autostrady przy spełnieniu warunków zadania.

예제 입력 1

10 19
10 7 9
7 10 100
10 7 77
5 4 3
3 9 4
3 5 6
1 4 1
10 1 7
8 9 8
2 9 3
10 5 5
8 10 6
3 1 9
5 2 7
2 3 2
7 4 8
10 4 1
5 6 1
10 6 2

예제 출력 1

8