Turist Hüseyn#10202
Hüseyn başqa bir ölkəyə getmək istədi, amma koronavirus dövründə ucuz marşrut tapmaq çətindir. Avtobus sürücüsünün öz ölkəsində şəhərin siyahısı var və o, bu şəhərlər arasında hansı marşrutların ən çox mənfəət gətirəcəyini hesablayıb. Hər bir yol iki şəhəri birləşdirir. Yolun dəyəri — sürücünün həmin marşrutu seçərsə əldə edəcəyi məbləğdir.
Elə bir yol dəsti seçmək lazımdır ki, onların hər hansı ikisi bir ortaq şəhərə malik olsun. Avtobus sürücüsünün əldə edə biləcəyi maksimum mümkün dəyəri hesablayın.
Birinci sətirdə iki tam ədəd verilir: şəhərlərin sayı n~(1 \le n \le 3 \cdot 10^5) və yolların sayı m~(1 \le m \le 5 \cdot 10^5). Şəhərlərin nömrələnməsi -dən -ə qədərdir.
Növbəti sətirin hər biri üç ədəd ehtiva edir: a_i, b_i~(1 \le a_i, b_i \le n) və p_i~(1 \le p_i \le 10^9 bütün üçün), burada a_i və b_i -ci yol ilə birləşdirilən şəhərlərdir və p_i həmin yolun dəyəridir. Zəmanət verilir ki, eyni şəhər cütünü birləşdirən iki yol yoxdur.
Bir ədəd - maksimum mümkün dəyəri çıxarın.
Birinci nümunə üçün izah
1 - 2, 1 - 3, 1 - 4 yollarını seçmək dəyərini verir və bu düzgün cavabdır. Həmçinin 1 - 2, 1 - 4, 2 - 4 yollarını da seçmək olar, amma bu halda dəyər daha az olur — .