Turist Hüseyn
Hüseyn ölkə daxilində səyahət etməyi qərara aldı, lakin koronavirus dönəmində avtobusla ucuz səyahətlər etmək çətin məsələdir. Ölkədə N sayda şəhər və bu şəhərləri birləşdirən M sayda birbaşa yol var. Avtobus sürücüsündə bu şəhərlərin, onlar arasındakı yolların və bu yolların qiymətlərinin siyahısı var. Hər bir yol iki şəhəri birləşdirir və yolun qiyməti bu yolu marşurutuna daxil etdiyi zaman sürücünün əldə etdiyi qazancı göstərir. Sürücü bir neçə yolu seçib onlar boyunca səyahət etmək üçün Hüseynə təklif edə bilər. Seçilmiş yolların istənilən ikisinin ortaq bir uc nöqtəsi (şəhəri) olmalıdır. Sürücü qazancını maksimum etməyə çalışır. Onun əldə edə biləcəyi maksimum qazancı tapın.
Qeyd: Hər hansı bir yol seçildiyi zaman, onun qiyməti yalnız bir dəfə hesablanır. Yəni sürücünün qazancının üzərinə bir dəfə gəlinir.
####Giriş:Birinci sətirdə iki tam ədəd N və M (1 ≤ N ≤ 300000,1 ≤ M ≤ 500000 ) uyğun olaraq şəhərlərin və yolların sayı, növbəti M sətrin hər birində isə üç tam ədəd a[i] , b[i] , p[i] (1 ≤ a[i] , b[i] ≤ N ,1 ≤ p[i] ≤ 10^9 ) yollar verilir. Hər hansı iki yol eyni şəhərləri birləşdirmir.
####Çıxış:Sürücünün əldə edə biləcəyi maksimum qazancı çap edin.
####İzah
1-2, 1-3 və 1-4 yollarını seçməklə 4 qazanc əldə etmək olar və bu doğru cavabdır. Siz 1-2, 1-4 və 2-4 yollarını da seçə bilərsiniz, lakin bu halda qazanc 3 olacaq.