Доработка программы С++

Нужно доделать код программы, в котором строится минимальное остовное дерево графа методом Прима.

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