Граф и весовая матрица: кратчайший путь по схеме

Схема дорог N-ского района представлена в виде графа: вершины — населённые пункты, рёбра — дороги между ними. Граф задан списком рёбер: А–Б, А–В, Б–Г, Б–Е, В–Г, В–Д, Г–Е, Д–Е, Д–Ж, Е–Ж. В таблице указана протяжённость каждой дороги (в километрах); пустая клетка означает, что прямой дороги между пунктами нет. Нумерация пунктов в таблице (П1, П2, …) никак не связана с буквенными обозначениями вершин графа.

Определите длину кратчайшего пути из пункта А в пункт Ж, если двигаться можно только по дорогам, указанным на схеме. В ответе запишите целое число.