Yanğínsöndürmə məntəqəsi#1059
Bir şəhərə bir neçə yanğínsöndürmə məntəqəsi xidmət edir. Bəzi sakinlər evlərindən ən yaxın yanğínsöndürmə məntəqəsinə olan məsafənin çox böyük olduğundan şikayət ediblər və yeni bir yanğínsöndürmə məntəqəsi tikilməsini tələb ediblər. Yeni məntəqənin yeri elə seçilməlidir ki, istənilən qovşaqdan ən yaxın yanğínsöndürmə məntəqəsinə olan maksimum məsafə minimallaşdırılsın.
Şəhərdə uzunluqları müxtəlif olan yollarla birləşdirilmiş ən çoxu qovşaq var. Heç bir qovşaqda -dən çox yol birləşmir. Həm evlər, həm də yanğínsöndürmə məntəqələri qovşaqlarda yerləşir (qovşaqdan faktiki binaya olan məsafə sıfır sayılır). Hər bir qovşaqda ən azı bir ev var. Bir qovşaqda bir neçə yanğínsöndürmə məntəqəsi ola bilər.
Birinci sətirdə iki müsbət tam ədəd var: (f \leq 100) — mövcud yanğínsöndürmə məntəqələrinin sayı və (i \leq 500) — qovşaqların sayı. Qovşaqlar -dən -yə qədər ardıcıl nömrələnib. Növbəti sətirin hər birində bir yanğínsöndürmə məntəqəsinin yerləşdiyi qovşağın nömrəsi verilib. Sonrakı sətirlərin hər birində üç müsbət tam ədəd var: yol ilə birləşdirilən iki qovşağın nömrəsi və həmin yolun uzunluğu. Bütün yollar ikitərəflidir və istənilən iki qovşaq arasında hansısa bir marşrut ilə əlaqə var.
Bir tam ədəd çıxışa verilir: istənilən qovşaqdan ən yaxın yanğínsöndürmə məntəqəsinə olan maksimum məsafəni minimallaşdırmaq üçün yeni yanğínsöndürmə məntəqəsi tikilməli olan ən kiçik qovşaq nömrəsi.
Nümunə 1