Benzin

Maddələr 1, 2, ..., N (N ≤ 150) arasında bir neçə yol mövcuddur. Hər bir yolun uzunluğu məlumdur. Bu yol sistemi vasitəsilə istənilən maddədən digərinə çatmaq mümkündür. Yanacaqdoldurma məntəqələri yalnız maddələrdə yerləşir. Avtomobilin bu yol sistemi ilə hərəkət edərək, istənilən maddədən digərinə problemsiz çatması üçün yanacaqsız keçə biləcəyi maksimum məsafəni müəyyən etmək lazımdır.

Giriş verilənləri

Giriş faylının ilk sətirində N və K (yolların sayı) ədədləri verilir. Sonrakı K sətirdə yollarla birləşdirilmiş maddə cütləri və aralarındakı məsafə — 0-dan böyük və 10000-i keçməyən tam ədəd kilometr göstərilir. K ≤ 150^2.

Çıxış verilənləri

Çıxış faylında bir ədəd olmalıdır — yanacaqsız keçilə bilən maksimum məsafənin uzunluğu.

Nümunələr