linnad={}
for rida in open("linnadkaugustega.txt", "r"):
   m=rida.strip().split()
   abim=[sona.split(":") for sona in m[1:]]
   linnad[m[0]]={}
   for paar in abim:
     linnad[m[0]][paar[0]]=int(paar[1])
print(linnad)

alglinn="Risti"
leitud=[{"nimetus":alglinn, "kaugus":0, "saabumiskoht":""}]
uuritud=[]
while leitud:
  uuritav=leitud.pop()
  for linn in linnad[uuritav["nimetus"]]:
    print(linn, uuritav["kaugus"]+linnad[uuritav["nimetus"]][linn])
    olemas=False
    lyhemad=[]
    for koht in leitud+uuritud:
      if koht["nimetus"]==linn:
         olemas=True
         print("leidis "+linn)
         if koht["kaugus"]>uuritav["kaugus"]+linnad[uuritav["nimetus"]][linn]:
           koht["kaugus"]=uuritav["kaugus"]+linnad[uuritav["nimetus"]][linn]
           koht["saabumiskoht"]=uuritav["nimetus"]
           print("tuli lyhem")
           lyhemad.append(koht)
         else: print("pole lyhem")
    for koht in lyhemad:
      uuritud.remove(koht)
      leitud.append(koht)
    if not olemas:
       leitud.append({"nimetus":linn, 
          "kaugus":uuritav["kaugus"]+linnad[uuritav["nimetus"]][linn],
          "saabumiskoht":uuritav["nimetus"]})
    print(leitud)
  uuritud.append(uuritav)
  #input()
    #Uuritute salvestamine puudu
               
print(uuritud)

def leiaUuritudLinn(nimetus):
   for linn in uuritud:
      if linn["nimetus"]==nimetus: return linn

sihtlinn="Keila"
teekond=[]
koht=leiaUuritudLinn(sihtlinn)
teekond.append(koht)
while koht["saabumiskoht"]!="":
   koht=leiaUuritudLinn(koht["saabumiskoht"])
   teekond.append(koht)
   
print(teekond)
teekond.reverse()

for linn in teekond: 
  print(linn["nimetus"], '-', linn["kaugus"])