Применяем к графу алгоритм Дейкстры. Объявляем конечную вершину текущей. В цикле с предусловием (цикл будет выполняться, пока текущая вершина не является первой) добавляем в массив вершин пути текущую вершину и изменяем ее на вершину, ей предыдущую. Теперь осталось только развернуть этот массив и вывести ответ.