Alex the Truck Driver
Python 2, 210 205

from itertools import*
r=range(input())
d={t:input()for t in combinations(r,2)}
n=0,
print" -&gt; ".join(chr(65+c)for c in n+min(permutations(r[1:]),key=lambda p:sum(d[min(t),max(t)]for t in zip(n+p,p+n)))+n)


Edit: Shortened according to Volatility's suggestion.
I'm amazed that it gets more readable and Pythonic the shorter it gets.