6) Иван-Царевич спешит выручить Марью-Царевну из плена Кощея. В таблице указана протяженность дорог между пунктами, через которые он может пройти. Укажите длину самого длинного участка кратчайшего пути от Ивана-Царевича до Марьи-Царевны (от точки И до точки М). Передвигаться можно только по дорогам, указанным в таблице.

По таблице есть, в частности, дороги И–Б длиной 1 и Б–М длиной 3. Путь И–Б–М имеет длину 1 + 3 = 4.

Сравним с другими возможными путями: напрямую И–М — 8; через Г — 6 + 1 = 7; путь И–А–В–Б–М — 1 + 1 + 2 + 3 = 7. Значит, кратчайший путь — И–Б–М, его длина равна 4.

Участки этого пути имеют длины 1 и 3; самый длинный из них равен 3.

Ответ: 3.