Given below is an undirected weighted connected graph:
Find a maximum spanning tree in the graph (i.e, a spanning tree having the maximum possible weight among all other spanning trees in the graph) using Prim's algorithm. Print your answer to the field below in the following format:
10
1 2
3 4
4 5The number in the first line is the total weight of a maximum spanning tree, the remaining lines are edges, each on a separate line.