Гляньте еще сюда http://e-maxx.ru/algo/mst_prim. Там приведены очень полезный оптимизации алгоритма, они существенно ускорят тривиальное решение.
По сути:
set {int} used;
vector {list {Edge}} edges;
vector {Edge} ans;
pr_queue {Edge} next_edges;
used.add(0);
edges.addAll(edges[0]);
while(!next_edges.empty()){
Edge edge = next_edges.front();
next_edges.pop();
if(!used.contains(edges.to)){
used.add(edges.to);
ans.add(edge);
next_edges.addAll(edges[edges.to]);
}
}