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}

alglinn="Valga"

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":0}
  uuritav=leiaUuritav()

print(m)