import java.util.*;

class Kaari {
    int alku;
    int loppu;
    int pituus;

    public Kaari(int alku, int loppu, int pituus) {
        this.alku = alku;
        this.loppu = loppu;
        this.pituus = pituus;
    }
}

public class Reitinhaku {
    static HashMap<String,Integer> tunnukset = new HashMap<>();
    static ArrayList<Kaari> kaaret = new ArrayList<>();
    static HashMap<Integer,String> takaisin = new HashMap<>();

    static int haeTunnus(String nimi) {
        if (tunnukset.containsKey(nimi)) {
            return tunnukset.get(nimi);
        }
        tunnukset.put(nimi,tunnukset.size()+1);
        takaisin.put(tunnukset.size(),nimi);
        return tunnukset.get(nimi);
    }

    static void lisaaYhteys(String nimi1, String nimi2, int pituus) {
        int tunnus1 = haeTunnus(nimi1);
        int tunnus2 = haeTunnus(nimi2);
        kaaret.add(new Kaari(tunnus1,tunnus2,pituus));
    }

    static void laskeReitit(String nimi) {
        int n = tunnukset.size();
        int[] etaisyys = new int[n+1];
        int INF = 999999999;
        for (int i = 1; i <= n; i++) {
            etaisyys[i] = INF;
        }
        etaisyys[haeTunnus(nimi)] = 0;
        while (true) {
            boolean muutos = false;
            for (Kaari k : kaaret) {
                if (etaisyys[k.alku]+k.pituus < etaisyys[k.loppu]) {
                    etaisyys[k.loppu] = etaisyys[k.alku]+k.pituus;
                    muutos = true;
                }
                if (etaisyys[k.loppu]+k.pituus < etaisyys[k.alku]) {
                    etaisyys[k.alku] = etaisyys[k.loppu]+k.pituus;
                    muutos = true;
                }
            }
            if (!muutos) break;
        }
        for (int i = 1; i <= n; i++) {
            System.out.println("etäisyys kaupunkiin "+takaisin.get(i)+" on "+etaisyys[i]);
        }
    }

    public static void main(String[] args) {
/*
      /----Oulu
  200/      |
Vaasa       |500
 |          |
 |315  120  |
 |   /--Tampere
Turku       |200
     \180   |
      Helsinki

      Tallinna
         |
       Tartto
*/
        lisaaYhteys("Helsinki","Turku",180);
        lisaaYhteys("Helsinki","Tampere",200);
        lisaaYhteys("Turku","Tampere",120);
        lisaaYhteys("Turku","Vaasa",315);
        lisaaYhteys("Tampere","Oulu",500);
        lisaaYhteys("Vaasa","Oulu",200);
        lisaaYhteys("Tallinna","Tartto",140);
        laskeReitit("Turku");
    }
}