В государстве Берляндия радость: у императора родился сын! В честь этого события во все города из столицы были посланы гонцы с этой вестью, по одному гонцу в каждый город. На карте Берляндия представляет собой 15 городов и 25 дорог. Каждая дорога имеет свою длину
в километрах. Каждый гонец бежит со скоростью 1 км/час. Гонцы стартуют в момент времени 0 и бегут самым коротким из всех возможных
путей. Для каждого города выведите время, через которое жители этого города получат радостную новость.
Ниже дана карта Берляндии. Числа в кружочках - номера городов, числа возле ребер - длина дороги в километрах. Столица имеет номер 1. https://www.letovo.online/common/uploads/images/chart%20(1).png_картинка