Ovçuluq
Лорд Bredli, minilliklər boyu nəsli kəsilmiş hesab edilən, lakin son zamanlarda Himalay dağlarında müşahidə edilən yeti ovuna çıxıb. Mükəmməl ovçu və qiymətli əşyaların həvəskarı olaraq, o, yetini tutmaq və dərisini kolleksiyasına əlavə etmək istəyir.
Qar adamı dağların mağara sistemində yaşayır. Lord Bredli qeyri-qanuni olaraq, müxtəlif uzunluqlu mağaralar və onları birləşdirən tunellərdən ibarət sistemin xəritəsini əldə edib. Maraqlıdır ki, sistem əlaqəlidir: hər iki mağara tunellər vasitəsilə bir yolla birləşdirilir. Veteran səyyah öz cəsarətinə güvənərək yetini dalana salmaq və onu yaxın döyüşdə məğlub etmək istəyir. Bunun üçün o, sizdən bəzi tunelləri məhv etməyi xahiş edir ki, hər iki mağara bir yolla birləşdirilsin (mağara qrafı ağaca çevrilməlidir).
Bredli heyvanın arxasınca çox uzun müddət qaçmaq istəmir - elə tunelləri məhv etmək lazımdır ki, ən uzaq iki mağara arasındakı məsafə minimal olsun.
Giriş verilənləri
Birinci sətir testlərin sayını t ehtiva edir. Sonra testlər gəlir.
Hər bir testin birinci sətiri iki natural ədəd ehtiva edir: n (n ≤ 500) və m (m ≤ 5000) - mağaraların və onların arasındakı tunellərin sayı. Növbəti m sətirin hər biri üç tam ədəd a, b və d (1 ≤ a, b ≤ n, 1 ≤ d ≤ 10^6) ehtiva edir, a və b mağaraları arasında uzunluğu d olan tuneli təsvir edir.
Çıxış verilənləri
Hər bir test üçün tunellərin məhv edilməsindən sonra iki mağara arasındakı ən böyük məsafənin mümkün olan ən kiçik dəyərini ayrıca sətirdə çıxarın (açıq-aydın ki, onlardan dəqiq m - n + 1 məhv edilməlidir).