Need help with clusters

[fraC19]

Hi, I'm currently working on an assignment which I need to input a file like this:

1 2 3 4
0 2 3
0 1 3     //connection between two vertexes 
0 1 2
0

0 3 4 5 2
3 0 2 4 -999  //weight of the edge that connect between two vertexes
4 2 0 1 -999  //-999 means there is no connection between two vertexes
5 4 1 0 -999
2 -999 -999 -999 0

2  //number of clusters 

I've done the first part of the assignment which I use prim's algorithm to find the shortest path to each vertex without causing cycle of the graph.
And I can print my output in this form:

 Edge    Weight
0 -  1     3
1 -  2     2
2 -  3     1
0 -  4     2

For the rest of the part, due to the last line of the input file, I need to cut the graph into 2 parts by deleting the highest weight of the edge in the graph, which is '3'.
So my output will be like this:

0 4
1 2 3

Can someone help me with some idea for how should I do to achieve that? Really appreciated!