Qraffiti

Verilmiş çəkili istiqamətsiz qraf n zirvə və m kənar ilə təqdim olunur. Bu qrafda döngələr yoxdur və müstəvidə çəkilə bilər. Nurlashko qrafı müstəvidə bərpa etdi və aşağıdakı qrafı qurdu: müstəvidəki üzlər (sahələr) zirvə oldu və onların arasında olan kənarlar bu üzlərə ortaq olan kənarlar oldu. Məsələn, əgər 2 üz ilkin qrafda ortaq kənara malik idisə, yeni qrafda üzlər arasında kənar əlavə edilməlidir. İndi Nurlashko yeni qrafın minimal örtük ağacını tapmaq istəyir. Minimal örtük ağacı - n zirvə ilə əlaqəli ağacdır ki, ağacın kənarlarının cəmi minimaldır.

Giriş məlumatları

Birinci sətir 2 tam ədəd n və m (3 ≤ n ≤ 1000000, 0 ≤ m ≤ 200000) ehtiva edir. Növbəti m sətirin hər biri 3 tam ədəd ehtiva edir: u, v, c (1 ≤ u, v ≤ n, u ≠ v, -10^6 ≤ c ≤ 10^6), burada u və v zirvələrdir, c onları birləşdirən kənarın çəkisidir.

Çıxış məlumatları

Bir tam ədəd çıxarın - minimal örtük ağacının çəkisi.