Самая короткая дорога. Между пунктами А, Б, В, Г и Д построены дороги. В таблице указана протяжённость каждой дороги в километрах, а прочерк означает, что прямой дороги нет. Проехать по бездорожью нельзя. Определи длину кратчайшего пути из А в Д и введи в ответ целое число.

Из А можно ехать в Б (4 км) или В (9 км). Проверим маршруты до Д:

• А → Б → В → Д: 4 + 2 + 7 = 13 км.
• А → Б → Г → Д: 4 + 8 + 2 = 14 км.
• А → В → Д: 9 + 7 = 16 км.

Кратчайший из этих путей проходит через Б и В.

Ответ: 13