In Mathematics this is called finding the Minimum Spanning Tree (MST) of a graph. It's very easy to do by hand, but it was a fun challenge to make an algorithm. I decided to replicate Prim's Algorithm because that was a 15 mark question on my final exam and I crushed it.
Before I start the algorithm I first sum all the values in the top right triangle, to get the old sum. Then we continue with the steps, verbatim from Wikipedia:
Initialise a tree with a single vertex, chosen arbitrarily from the graph.
Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
Repeat step 2 (until all vertices are in the tree).
My code is including below!
No interactive code for this problem, my code is given below.