Ferm və fabrik
Əziz Baitlendin kralı Bitolomey sizi salamlayır!
Kral Bitolomey hesab edir ki, Baitlend olduqca unikal bir ölkədir. O, kifayət qədər kiçikdir və bütün vətəndaşları (kral istisna olmaqla) ya fermada, ya da iki fərqli şəhərdə yerləşən fabrikdə işləyirlər. Beləliklə, hər səhər hər şəhərin sakinləri bu iki şəhərə böyük tıxaclarda gedirlər.
Baitlendin yol şəbəkəsi müxtəlif şəhər cütlərini birləşdirən ikitərəfli yollardan ibarətdir. Yollar şəhərlərdən kənarda kəsişmir (lakin tunellər və körpülər yarana bilər). İki şəhər arasında bir neçə birbaşa yol ola bilər. Ferma və fabrik bütün şəhərlərdən əlçatandır.
Bir neçə ay əvvəl, yol hərəkəti vəziyyətini yaxşılaşdırmağa çalışaraq, kral Bitolomey vətəndaşlardan hər dəfə yoldan istifadə etdikdə sabit bir məbləğ ödəmələrini tələb edərək yol haqqı tətbiq etdi. Bitolomey ümid edirdi ki, pul ödəmək perspektivi bəzi vətəndaşları marşrutlarını yenidən nəzərdən keçirməyə məcbur edəcək və bununla da trafiki daha bərabər paylayacaq.
Kralın ideyası, məsləhətçilərinin dediyinə görə, mükəmməl olmadı. İndi Baitlendin hər bir vətəndaşı işə getmək üçün ən ucuz marşrutu istifadə edir! Kral Bitolomey bu barədə çox narahat deyil, çünki yığılan gəlirlər həqiqətən krallığın büdcəsini yaxşılaşdırdı. Əslində, kralın maliyyə vəziyyəti o qədər yaxşıdır ki, o, özünə yeni bir paytaxt və orada yeni bir qala tikməyi planlaşdırır. Bu yeni paytaxt bəzi digər şəhərlərlə birbaşa yollarla birləşdirilməlidir ki, oradan hər hansı bir şəhərə çatmaq mümkün olsun. Yenidən yaradılan yollar hər hansı bir qeyri-mənfi yol haqqına malik ola bilər (xüsusilə, yol haqları mütləq tam ədəd olmamalıdır).
Kral Bitolomey həqiqətən də qəsrinin yanından keçən maşınların yaratdığı səs-küyü sevmir. O, yeni paytaxtdan çıxan yeni yollar üçün elə bir yol haqqı təyin etmək istəyir ki, paytaxtdan başqa hər hansı bir v şəhəri üçün fermaya və fabrikə gedən ən ucuz yollar paytaxtdan keçməsin (nəzərə alın ki, v həmçinin ferma və ya fabrik olan bir şəhər ola bilər). Digər tərəfdən, kral rüsumlardan azad olmadığı üçün yeni paytaxtdan hər hansı digər şəhərə ən ucuz yolların orta qiymətini minimallaşdırmaq istəyir.
Kralın minimal mümkün qiyməti müəyyən etməsinə kömək edin.
Giriş Məlumatları
Birinci sətir testlərin sayı t-ni ehtiva edir. Testlərin təsvirləri aşağıda verilmişdir:
Hər bir test n, m tam ədədləri ilə başlayır (2 ≤ n ≤ 10^5, 1 ≤ m ≤ 3 * 10^5), Baitlenddəki şəhərlərin və yolların sayını göstərir. Növbəti m sətir yolları təsvir edir. Hər bir yol üç tam ədəd u, v, c (1 ≤ u, v ≤ n, u ≠ v, 0 ≤ c ≤ 10^6) ilə verilir - iki şəhəri birləşdirən yolun indeksləri və kralın bu yol üçün təyin etdiyi haqq. Hər hansı bir şəhər cütü arasında bir neçə yol ola bilər.
Fermanın və fabrikin şəhər indeksləri müvafiq olaraq 1 və 2-dir.
Çıxış Məlumatları
Hər bir test üçün yeni yaradılan paytaxtdan digər şəhərlərə ən ucuz yolun mümkün olan minimal orta qiymətini ayrıca sətirdə çıxarın. Cavabı 10^(-8)-dən çox olmayan səhvlə verin.