woogle.we
Bilirsinizmi ki, payızda insanlar daha yaxşı işləyirlər? Bunun səbəbi qədim zamanlarda hər payız məhsul yığılmasıdır.
Təmirlən, Woogle ofisləri arasında səyahət etməyə qərar verib. Bəzi ofislər arasında bir neçə ikitərəfli yollar mövcuddur və bu yolların hər biri müəyyən miqdarda vollara başa gəlir. Təmirlənin məhdudiyyətsiz miqdarda vollara sahib olduğunu fərz edə bilərik. O, bu yolları Waspi kartı ilə ödəyir. Diqqət yetirin ki, Təmirlən bütün ofis cütləri arasında səyahət edə bilər və orada öz-özünə qapanan yollar yoxdur. Aydana Təmirlən üçün narahatdır və onun bu səyahətə daha az pul xərcləməsini istəyir. O, kartına minimal mümkün limiti təyin etmək istəyir (bu qızları kim başa düşər?) ki, Təmirlən fərqi hiss etməsin. Bu o deməkdir ki, əgər Təmirlən ofis A-dan ofis B-yə ən ucuz yolla gedirsə (o həmişə optimal şəkildə gedir, ACM vərdişi), onda onun səyahət zamanı heç bir ödənişi limit məhdudiyyətinə görə rədd edilməyəcək, hər hansı ofis A və B üçün.
Aydanaya Təmirlənin hər hansı ofisdən hər hansı ofisə optimal şəkildə çatması üçün kartına təyin edə biləcəyi minimal vollar miqdarını seçməyə kömək edin.
Giriş məlumatları
Birinci sətir iki tam ədəd n, m (2 ≤ n ≤ 100, 1 ≤ m ≤ n * (n - 1) / 2) - ofislərin və onların arasındakı yolların sayını ehtiva edir.
Növbəti m sətirin hər biri üç qeyri-mənfi tam ədəd v, u, w (1 ≤ v, u ≤ n, 1 ≤ w ≤ 10^5) - ofislərin nömrələri və yolun dəyərini ehtiva edir.
Çıxış məlumatları
Bir tam ədəd çıxarın - Təmirlənin kartı üçün minimal limit.