Алгоритмы на графах

Требуется: реализовать алгоритм построения минимального остовного дерева для заданного связного неориентированного графа.

Какой алгоритм применять:

• Если ваша фамилия начинается с буквы «А»,… «Л», то нужно применять алгоритм Краскала.
• Если ваша фамилия начинается с буквы «М»,… «Я», то нужно применять алгоритм Прима.

Формат входных данных

В первой строке - последовательность имён вершин, разделённых пробелами.

В последующих строках - описания рёбер и их весов. В каждой строке: имя начальной вершины ребра, имя конечной вершины ребра, вес ребра (вещественное число) -  разделены пробелами.

Формат выходных данных

В первой строке должно быть одно вещественное число - вес минимального остовного дерева.

В последующих строках должны быть рёбра, вошедшие в минимальное остовное дерево (имя начально вершины, пробел, имя конечной вершины).

Примеры прикреплены к заданию.

За полностью сданное задание: 6 баллов.

За успешную сдачу до раннего срока (01.11.24 включительно): +2 балла.