Şosse Tikintisi#4227
Başqa Yola Çıxış Hərəkatının (BYÇH) rəhbəri olaraq, şəhərinizdə yeni bir magistral yol tikilməsi üçün bələdiyyə başçısına müraciət edirsiniz. Bu gün sizin şanslı gününüzdür, çünki müraciətiniz təsdiqləndi. Lakin bir şərt var: Ən yaxşı magistral yol arteriyasının planını təqdim etməlisiniz, əks halda bu baş verməyəcək!
Əlinizdə şəhərinizdəki bütün icmaları göstərən bir xəritə var, hər biri unikal bir nömrə ilə, harada magistral yol çıxışları yerləşdirə bilərsiniz. Xəritədə icmalar arasında sürüş məsafələri ilə etiketlənmiş bir sıra yollar var ki, bunları magistral yol xətti ilə əvəz edə bilərsiniz. Bu yol şəbəkəsindən istifadə edərək, hər hansı bir icmadan digərinə yalnız bir marşrut var. Başqa sözlə, icma A-dan icma B-yə aparan iki fərqli yol dəsti yoxdur.
İstədiyiniz iki icma arasında irəli-geri hərəkət edən bir magistral yol tikə bilərsiniz. Bu, həmin iki icma arasındakı unikal yol dəstini əvəz edəcək və yolda hər icmada bir çıxış tikiləcək. Təbii ki, çıxışı olmayan icmaların sakinləri yeni magistral yola çıxmaq üçün ən yaxın çıxışa getməli olacaqlar.
Uzun sürüşlər çox arzuolunmaz olduğundan, magistral yolu elə tikəcəksiniz ki, hər hansı bir icmadan ən yaxın çıxışa qədər olan ən uzun məsafə minimuma endirilsin. Şəhərinizin yollar və sürüş məsafələri ilə xəritəsi verildikdə, yeni magistral yol tamamlandıqdan sonra hər hansı bir icmadan ən yaxın çıxışa qədər olan ən uzaq məsafə nə qədər olacaq?
Giriş bir neçə test halından ibarətdir. Hər test halı bir şəhər xəritəsinin təsviridir və bir tam ədəd N (2 ≤ N ≤ 100000) ilə başlayır, bu da şəhərdəki icmaların sayını göstərir. Sonra N-1 sətir gəlir, hər biri üç tam ədəd, i, j (1 ≤ i, j ≤ n) və d (1 ≤ d ≤ 10000) ehtiva edir. Hər sətir icmalar i və j arasında sürüş məsafəsi d olan bir yol olduğunu göstərir. Giriş N = 0 olan bir sətirlə bitir, bu işlənməməlidir.
Hər bir şəhər xəritəsi üçün, yeni magistral yolun ən yaxın çıxışına qədər olan ən uzaq məsafəni bir sətirdə çıxarın.
Nümunə 1