Минимизировать стоимость строительства дорог

Нас толкоM не учили такоMу програMMированию, но препод дал такую задачку для решения:

Три страны решили объединиться в союзное государство. Так как чиновникам предстоит часто ездить из одной столицы в другую, необходимо заасфальтировать некоторые дороги (в настоящий момент все дороги являются гравийными) таким образом, чтобы можно было проехать между двумя любыми столицами по хорошей дороге (необязательно, чтобы путь был кратчайшим).
Напишите программу, которая определит, какие дороги нужно заасфальтировать, чтобы общая стоимость строительства была минимальной. Стоимость строительства линейно зависит от длины асфальтируемой дороги.
Формат ввода
Первая строка ввода содержит два целых числа: количество городов N (3 ≤ N ≤ 2000) и количество дорог
M (N−1 ≤ M ≤ N * ( N-1/2)
Далее следует M строк, содержащих по три целых числа: номера городов ai и bi (1 ≤ ai, bi ≤ N, ai ≠ bi), связанных гравийной дорогой, и длина дороги di (1 ≤ di ≤ 10 000). Движение по дорогам возможно в обе стороны. Гарантируется, что существует путь между двумя любыми городами и в графе нет кратных ребер и петель. Столицами стран являются города с номерами 1, 2 и 3.
Формат вывода
В первой строке вывести количество асфальтируемых дорог, во второй строке — их номера (от 1 до M в соответствии со списком дорог во входном файле) через пробел в произвольном порядке. Если существует несколько вариантов, минимизирующих стоимость строительства, можно вывести любой из них.
Пример ввода
6 7
1 6 1
1 3 10
1 5 3
2 5 6
3 4 2
3 5 4
5 6 5
Вывод для примера
3
3 4 6
ПоMогите пожааалуйста.

0

1) Маршруты А-Б, Б-В, В-А очевидно, должны пересекаться в некой точке Г.
2) Эта точка пересечения должна быть одна (нафиг больше?).
3) Маршруты Г-А, Г-Б и Г-В, очевидно, должны представлять собой кратчайший маршрут между двумя точками.
Перебираете все варианты Г, ищете кратчайшие маршруты Г-А, Г-Б и Г-В (гуглите волновой алгоритм), выбираете из просмотренных вариантов наилучший.

PS А кодьте все это дело сами, я лишь наколеночную идею подсказал.

0