Вывести точки графа в текст файл через которые находится минимальный путь по Флойду

[Makspane]

Написал программу, ЗАПРАВКА, но препод потребовал, чтоб эта программа выводила еще в текстовый файл еще и номера городов , по которым проежает авто с первого в последнюю току...
Я никак не пойму как это сделать, есле кто может. очень прошу вашей помощи, ....заранее очень благодарен
в архиве программа.., не писал код, так как очень длиннный.

вот ее условие
В стране N городов, некоторые из которых соединены между собой дорогами.
Для того, чтобы проехать по одной дороге требуется один бак бензина.
В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться
из первого города в N-ый, потратив как можно меньшее количество денег.

Входные данные
Во входном файле записано сначала число N (1≤N≤100), затем идет
N чисел, i-ое из которых задает стоимость бензина в
i-ом городе (все это целые числа из диапазона от 0 до 100).
Затем идет число M - количество дорог в стране, далее идет описание
самих дорог. Каждая дорога задается двумя числами - номерами городов,
которые она соединяет. Все дороги двухсторонние (то есть по ним можно
ездить как в одну, так и в другую сторону), между двумя городами всегда
существует не более одной дороги, не существует дорог, ведущих
из города в себя.

Выходные данные
В выходной файл выведите одно число - суммарную стоимость маршрута
или -1, если добраться невозможно.
__________________________
Пример входного файла
4
1 10 2 15
4
1 2 1 3 4 2 4 3

Пример выходного файла
3

_______________________

Пример входного файла
4
1 10 2 15
0

Пример выходного файла
-1