Ağacın medianı#4293
Sizə cüt sayda düyünə malik olan bir bağlı istiqamətsiz qraf verilir. Bağlı qraf odur ki, oradakı bütün düyünlər birbaşa və ya dolayısı ilə kənarlarla bir-birinə bağlıdır.
Tapşırığınız bütün düyünləri əhatə edən elə bir skelet ağac (spanning tree) tapmaqdır ki, həmin ağacdakı kənarların qiymətlərinin medianı mümkün olan ən kiçik olsun. Skelet ağacı — qrafın bütün düyünlərini əhatə edən ağacdır.
Giriş bir neçə datasetdən ibarətdir.
Hər datasetin formatı aşağıdakı kimidir:
s_1\ t_1\ c_1
s_m\ t_m\ c_m
Birinci sətrdə cüt ədəd (2 \leq n \leq 1000) və tam ədəd (n-1 \leq m \leq 10000) verilir. — düyünlərin, isə qrafdakı kənarların sayıdır.
Sonra növbəti sətrin hər birində s_i (1 \leq s_i \leq n), t_i (1 \leq t_i \leq n, t_i \neq s_i) və c_i (1 \leq c_i \leq 1000) verilir.
Bu o deməkdir ki, s_i və t_i düyünləri arasında qiyməti c_i olan bir kənar mövcuddur. Hər iki düyün cütünü birləşdirən bir kənardan artıq olmur.
Giriş n = 0 və m = 0 olduqda başa çatır. Bu halda proqram heç bir çıxış verməməlidir.
Hər dataset üçün cavab kimi bir sətirdə median dəyəri çap edin.
Nümunə 1