Известны расстояния в километрах между некоторыми городами. Вся информация записана в виде треугольной таблицы. Разумеется, между каждыми двумя городами можно передвигаться в обоих направлениях. Найдите такой маршрут от города Энск в город Знаменск, чтобы суммарная длина пути была минимальной. В ответе укажите суммарную длину пути такого маршрута.
| |
Ветлуги |
Версты |
Гусли |
Добро |
Знаменск |
Краев |
Лисов |
| Энск |
15 |
27 |
6 |
16 |
40 |
8 |
29 |
| Ветлуги |
|
3 |
8 |
19 |
30 |
12 |
4 |
| Версты |
|
|
17 |
17 |
3 |
11 |
9 |
| Гусли |
|
|
|
21 |
20 |
14 |
25 |
| Добро |
|
|
|
|
6 |
30 |
10 |
| Знаменск |
|
|
|
|
|
25 |
13 |
| Краев |
|
|
|
|
|
|
4 |