Tunel Şəbəkəsinin Optimallaşdırılması#5549
Ekspedisiyası yaxınlarda Himalaylarda kəşf edilmiş qədim mağara sistemini öyrənir. Sistem müxtəlif uzunluqda tunellərlə birləşmiş bir neçə mağaradan ibarətdir. Araşdırmaçılar bütün mağaralar və tunelləri göstərən xəritə əldə ediblər. Maraqlıdır ki, mağara sistemi bağlıdır: istənilən iki mağara arasında tunellərin müəyyən ardıcıllığı ilə getmək mümkündür.
Strukturu təhlil etmək üçün tədqiqatçılar şəbəkəni sadələşdirməyə qərar verirlər; belə ki, bəzi tunelləri silərək hər bir mağara cütü arasında yalnız bir unikal yol qalsın (yəni, sistem ağaca çevrilir). Lakin mağaralarda gedişi asanlaşdırmaq üçün istəyirlər ki, bunu elə etsinlər ki, istənilən iki mağara arasında məsafənin maksimum dəyəri mümkün qədər kiçik olsun.
Birinci sətirdə testlərin sayı verilir. Daha sonra test təsvirləri gəlir.
Hər test təsvirinin birinci sətrində iki natural ədəd yerləşir: mağaraların sayı n~(n \le 500) və tunellərin sayı m~(m \le 5000). Sonra hər biri sətrdən ibarət sətir gəlir, hər sətirdə üç ədəd , və d~(1 \le a, b \le n,~1 \le d \le 10^6) yazılıb, hansı ki, və mağaralarını birləşdirən uzunluğu olan bir tuneli təsvir edir.
Hər test üçün ayrıca sətrdə, artıq tunellər çıxarıldıqdan sonra istənilən iki mağara arasında məsafənin maksimum mümkün ən kiçik qiymətini çap edin (açıq-aydındır ki, məhz m - n + 1 tunel çıxarılmalıdır).
Nümunə 1