Ən yaxşı xizək marşrutu

John qışı sevir. Hər xizək mövsümündə o, dostları ilə birlikdə xizək sürməyə gedir. Bunun üçün onlar Alp dağlarının istənilən zirvəsinə birbaşa çatdıran helikopter icarəyə götürürlər. Oradan isə onlar toxunulmamış qar üzərində mənzərəli yamaclarla aşağıya doğru sürüşürlər.

Əlbəttə, onlar yalnız ən yaxşı qar və hava şəraitində xizək sürmək istəyirlər. Bunun üçün birləşdirilmiş şərait göstəricisindən istifadə edərək hər hansı bir gün üçün bütün mövcud yamacları qiymətləndirirlər.

Onlara ən möhtəşəm marşrutu tapmaqda kömək edə bilərsənmi?

Giriş verilənləri

Birinci sətirdə $n(2\le n\le 1000)$ və $m(1\le m\le 5000)$ iki tam ədəd verilir. Burada $n$ yamaclar arasında birləşdirici nöqtələrin ($1$-indeksli) sayı, $m$ isə yamacların sayıdır.

Növbəti $m$ sətirin hər biri üç tam ədəd $s,t,c(1\le s,t\le n,1\le c\le 100)$ ehtiva edir. Burada $s$ nöqtəsindən $t$ nöqtəsinə qədər olan yamac və şərait ölçüsü $c$ ilə təmsil olunur.

Giriş yamacları olmayan nöqtələr gözəl mənzərələri olan dağ zirvələridir, çıxış yamacları olmayan nöqtələr isə vadilərdir. Helikopter istənilən birləşdirici nöqtəyə enə bilər, buna görə dostlar turu istədikləri nöqtədə başlaya və bitirə bilərlər. Bütün yamaclar aşağıya doğru gedir, buna görə də haradan başlasalar da, yamaclardan keçdikdən sonra eyni nöqtəyə yenidən çata bilməzlər.

Çıxış verilənləri

Bir ədəd çıxarın — dostların keçə biləcəyi yolda şərait ölçülərinin maksimum cəmi.

Nümunələr