This was definitely a challenging problem. At first I had no idea what it was asking me for. But after reading some on Wikipedia about networks and graph theory, it made more sense.
I used the Prim’s algorithm entry on Wikipedia to help me implement an effective algorithm.
f = open('network.txt', 'r')
network = []
old_total = 0
for r in f:
r = r[:-2].split(',')
for i in range(len(r)):
if r[i] == '-':
r[i] = 10**3
else:
r[i] = int(r[i])
old_total += r[i]/2.0
network.append(r)
nodes_used = [0]
total = 0
while sorted(nodes_used) != range(40):
next = min(min(network[i]) for i in nodes_used)
for i in nodes_used:
if next in network[i]:
index = [i,network[i].index(next)]
if index[1] not in nodes_used:
total += next
nodes_used.append(index[1])
network[index[0]][index[1]] = 10**3
print int(old_total - total)