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:
No interactive code for this problem, my code is given below.