linnad={}
linnad["Tallinn"]={"Tapa": 80}
linnad["Tapa"]={"Tallinn":80, "Tartu": 112, "Rakvere": 30}
linnad["Rakvere"]={"Tapa":30, "Narva":120}
linnad["Narva"]={"Rakvere": 120}
linnad["Tartu"]={"Tapa":112,"Elva":25,"Petseri":85}
linnad["Elva"]={"Tartu":25, "Puka": 35}
linnad["Puka"]={"Elva": 35, "Valga": 30}
linnad["Valga"]={"Puka": 30, "Petseri": 90}
linnad["Petseri"]={"Tartu": 85, "Valga": 90}
linnad["Lavassaare"]={"Tootsi": 30}
linnad["Tootsi"]={"Lavassaare": 30}

alglinn="Petseri"


def leiaUuritav():
  for linn in m.keys():
    if m[linn]["uurida"]==1:return linn
  return False

m={alglinn:{"kaugus":0, "kust":"", "uurida":1}}
uuritav=leiaUuritav()
while uuritav:
  m[uuritav]["uurida"]=0
  for uus in linnad[uuritav].keys():
    if uus not in m.keys():
      m[uus]={"kaugus": m[uuritav]["kaugus"]+linnad[uuritav][uus],
              "kust": uuritav, "uurida":1}
    else:
      if m[uuritav]["kaugus"]+linnad[uuritav][uus]<m[uus]["kaugus"]:
         m[uus]["kaugus"]=m[uuritav]["kaugus"]+linnad[uuritav][uus]
         m[uus]["kust"]=uuritav
         m[uus]["uurida"]=1
  uuritav=leiaUuritav()

print(m)


#Tryki v2lja lyhimate teede puu alates alglinnast koos kaugustega

def trykiKohad(kust, tase):
   for linn in m.keys():
     if m[linn]["kust"]==kust:
       print("   "*tase, linn, m[linn]["kaugus"])
       trykiKohad(linn, tase+1)

trykiKohad("", 0)