Yanğın deposu
Şəhər bir neçə yanğınsöndürmə deposu ilə xidmət göstərilir. Bəzi sakinlər evlərindən ən yaxın yanğınsöndürmə deposuna olan məsafənin çox böyük olduğunu bildirərək yeni bir depo tikilməsini tələb edirlər. Yeni deponun yerini elə seçmək lazımdır ki, narazı sakinlərdən ən yaxın depoya olan məsafə mümkün qədər az olsun.
Şəhər maksimum 500 kəsişmədən ibarətdir və bu kəsişmələr müxtəlif uzunluqlu yollarla birləşdirilib. Bir kəsişmədə ən çox 20 yol ola bilər. Ev və yanğınsöndürmə depoları kəsişmələrdə yerləşir (kəsişmədən evə olan məsafə sıfır hesab olunur). Hər bir kəsişmədə ən azı bir ev var. Bir kəsişmədə bir neçə yanğınsöndürmə deposu ola bilər.
Giriş verilənləri
Birinci sətir iki natural ədəd ehtiva edir: mövcud yanğınsöndürmə depolarının sayı f (f ≤ 100) və kəsişmələrin sayı i (i ≤ 500). Kəsişmələr 1-dən i-yə qədər ardıcıl nömrələnib. Sonra f sətir gəlir, hər biri yanğınsöndürmə deposunun yerləşdiyi kəsişmənin nömrəsini ehtiva edir. Növbəti sətirlərdən hər biri üç natural ədəd ehtiva edir: ilk iki ədəd yol ilə birləşdirilmiş kəsişmələrin nömrələri, üçüncü ədəd isə bu yolun uzunluğudur. Bütün yollarda hər iki istiqamətdə hərəkət etmək mümkündür və istənilən iki kəsişmə arasında yol mövcuddur.
Çıxış verilənləri
Bir ədəd çıxarılmalıdır: yeni yanğınsöndürmə deposunun tikilməli olduğu kəsişmənin ən kiçik nömrəsi ki, istənilən kəsişmədən ən yaxın yanğınsöndürmə deposuna olan ən böyük məsafə minimum olsun.