Slim Span#5831
Verilmiş istiqamətsiz çəkili qraf G üçün müəyyən edilmiş bir skelet ağacı tapmalısınız.
Qraf G bir cüt (V, E)-dən ibarətdir, burada V zirvələr dəstidir {v_1, v_2, ..., v_n} və E istiqamətsiz kənarların dəstidir {e_1, e_2, ..., e_m}. Hər bir kənarın e çəkisi w(e) ilə göstərilir.
Skelet ağacı T, bütün n zirvələri n−1 kənarla birləşdirən dövrsüz əlaqəli alt qrafdır. Skelet ağacının T incəliyi, T-nin n−1 kənarları arasında ən böyük çəki ilə ən kiçik çəki arasındakı fərq kimi müəyyən edilir.
Məsələn, Şəkil 1(a)-da göstərilən qraf G dörd zirvəyə malikdir {v_1, v_2, v_3, v_4} və beş istiqamətsiz kənara malikdir {e_1, e_2, e_3, e_4, e_5}. Kənarların çəkiləri w(e_1) = 3, w(e_2) = 5, w(e_3) = 6, w(e_4) = 6, w(e_5) = 7 olaraq Şəkil 1(b)-də göstərilmişdir.
Şəkil 2: G qrafının skelet ağaclarının nümunələri
G üçün bir neçə skelet ağacı mövcuddur. Onlardan dördü Şəkil 2(a)'(d)-də təsvir edilmişdir. Şəkil 2(a)-dəki skelet ağacı T_a üç kənara malikdir, onların çəkiləri 3, 6 və 7-dir. Ən böyük çəki 7 və ən kiçik çəki 3 olduğundan, T_a ağacının incəliyi 4-dür. Şəkil 2(b), (c) və (d)-də göstərilən skelet ağaclarının T_b, T_c və T_d incəlikləri müvafiq olaraq 3, 2 və 1-dir. Asanlıqla görmək olar ki, hər hansı digər skelet ağacının incəliyi 1-dən böyük və ya bərabərdir, beləliklə Şəkil 2(d)-dəki T_d skelet ağacı ən incə skelet ağaclarından biridir və onun incəliyi 1-dir.
Sizin işiniz ən kiçik incəliyi hesablayan bir proqram yazmaqdır.
Giriş bir neçə datasetdən ibarətdir, ardınca boşluqla ayrılmış iki sıfır olan bir sətir gəlir. Hər bir dataset aşağıdakı formatdadır.
n m
a_1 b_1 w_1
...
a_m b_m w_m
Hər bir datasetdəki giriş elementi qeyri-mənfi tam ədəddir. Sətirdəki elementlər boşluqla ayrılır.
n zirvələrin sayı və m kənarların sayıdır. Siz 2 ≤ n ≤ 100 və 0 ≤ m ≤ n(n−1)/2 olduğunu qəbul edə bilərsiniz. a_k və b_k (k = 1, ..., m) müsbət tam ədədlərdir və n-dən kiçik və ya bərabərdir, bu da k-cı kənar e_k ilə birləşdirilən iki zirvəni v_a_k və v_b_k təmsil edir. w_k e_k kənarının çəkisini göstərən 10000-dən kiçik və ya bərabər müsbət tam ədəddir. Siz qəbul edə bilərsiniz ki, qraf G = (V, E) sadədir, yəni özünə döngələr (eyni zirvəni birləşdirən) və paralel kənarlar (hər iki ucu eyni olan iki və ya daha çox kənar) yoxdur.
Hər bir dataset üçün, əgər qrafın skelet ağacları varsa, onların arasında ən kiçik incəlik çap olunmalıdır. Əks halda, −1 çap olunmalıdır. Çıxış əlavə simvollar içerməməlidir.
Nümunə 1