#!/usr/bin/env python3

def parse(fname):
    with open(fname) as f:
        r = f.read()
    r = [line.split(',') for line in r.split('\n')[:-1]]
    weights = {a : [(b, int(w)) for b, w in enumerate(line)
                                   if w!='-'
                   ]
                   for a, line in enumerate(r)
              }
    return weights

def search(network, visited={0}):
    if len(visited) == len(network):
        return 0
    edges = [(n2, w) for node in visited
                   for n2, w in network[node]
                   if n2 not in visited
            ]
    next, w = min(edges, key = lambda x: x[1])
    return w + search(network, visited | {next})

network = parse("data/107_network.txt")
total_weight  = sum(w for node in network
                     for _, w in network[node])
total_weight //= 2
min_weight    = search(network)

print(total_weight - min_weight)