http://www.codechef.com/NOV12/problems/TOURMAP
my code:
#!/usr/bin/python
d1={}
d2={}
d3={}
test=input()
while test:
n=input()
num=0
for i in range(n-1):
s=raw_input().split()
d1[s[0]]=s[1]
d3[s[0]]=s[2]
num=num+int(s[2][:-1])
if d2.has_key(s[0]):
d2[s[0]]=d2[s[0]]+1
else:
d2[s[0]]=5
if d2.has_key(s[1]):
d2[s[1]]=d2[s[1]]+1
else:
d2[s[1]]=1
for city,value in d2.iteritems():
if value == 5:
s=city
break
for i in range(n-1):
print city,d1[city],d3[city]
city=d1[city]
print str(num)+"$"
test=test-1