Alex the Truck Driver Alex is a Truck Driver who wants to find the quickest way to deliver goods to multiple cities. He knows the distances between his destinations, but you need to write a program to help him find the quickest way to deliver goods to them.

Input

The first line of input gives the number of cities Alex needs to deliver goods to. Every line that follows gives the distance between the cities. The second line of input is always the distance between the first and second cities. If there is a third city, the third line of input is the distance between the first and third city. When to distance to the first city has been given for all cities, the next lines of input gives the distance between the the second city and every other city (except the first, as that information as already been given). This continues until every combination has been given. Sample inputs:

//Number of cities
4
//A -&gt; B
2
//A -&gt; C
4
//A -&gt; D
3
//B -&gt; C
5
//B -&gt; D
1
//C -&gt; D
3



3
6
4
2


Output

The output should print the quickest way to deliver goods to every destination in the form A -&gt; C -&gt; D -&gt; C -&gt; A (For every output, the reverse of will also work. You only need to print one solution). Alex ALWAYS starts at A and must always return to A at the end (as A is where he lives). Here are the outputs for the sample inputs above:

A -&gt; B -&gt; D -&gt; C -&gt; A



A -&gt; C -&gt; B -&gt; A


Rules

The shortest code wins.

Happy Golfing!
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.