import java.util.*;
public class Reitit {

    private HashMap<String, Solmu> verkko = new HashMap<>();

    public class Kaari {
        public String alku, loppu;
        int pituus;

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

    public class Solmu implements Comparable<Solmu> {
        public final String nimi;
        public int etaisyys = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
        public Solmu edellinen = null;
        public final Map<Solmu, Integer> naapurit = new HashMap<>();

        public Solmu(String nimi) {
            this.nimi = nimi;
        }

        public int compareTo(Solmu toinen) {
            if (etaisyys == toinen.etaisyys)
                return nimi.compareTo(toinen.nimi);
            return Integer.compare(etaisyys, toinen.etaisyys);
        }

    }

    List<Kaari> kaaret = new ArrayList<>(10000);

    @SuppressWarnings("Duplicates")
    public void lisaaTie(String alku, String loppu, int pituus) {
        Kaari kaari1 = new Kaari(alku, loppu, pituus);
        Kaari kaari2 = new Kaari(loppu, alku, pituus);

        kaaret.add(kaari1);
        kaaret.add(kaari2);
    }

    public int reitinPituus(String alku, String loppu) {
        luoVerkko();
        dijkstra(alku);
        return lyhyinPolku(loppu);
    }

    private void luoVerkko() {

        verkko = new HashMap<>(kaaret.size());

        for( Kaari kaari : kaaret) {
            if( !verkko.containsKey(kaari.alku)) verkko.put(kaari.alku, new Solmu(kaari.alku));
            if( !verkko.containsKey(kaari.loppu)) verkko.put(kaari.loppu, new Solmu(kaari.loppu));
        }
        for( Kaari kaari : kaaret) {
            verkko.get(kaari.alku).naapurit.put(verkko.get(kaari.loppu), kaari.pituus);
        }
    }


    public void dijkstra(String alku) {
        if (!verkko.containsKey(alku)) {
            System.err.printf("Verkossa ei ole solmua\"%s\"\n", alku);
            return;
        }
        final Solmu source = verkko.get(alku);
        NavigableSet<Solmu> q = new TreeSet<>();

        // set-up vertices
        for (Solmu v : verkko.values()) {
            v.edellinen = v == source ? source : null;
            v.etaisyys = v == source ? 0 : Integer.MAX_VALUE;
            q.add(v);
        }

        dijkstra(q);
    }

    private void dijkstra(final NavigableSet<Solmu> q) {
        Solmu u, v;
        while (!q.isEmpty()) {

            u = q.pollFirst();
            if (u.etaisyys == Integer.MAX_VALUE)
                break;

            for (Map.Entry<Solmu, Integer> a : u.naapurit.entrySet()) {
                v = a.getKey(); //the neighbour in this iteration

                final int alternateDist = u.etaisyys + a.getValue();
                if (alternateDist < v.etaisyys) {
                    q.remove(v);
                    v.etaisyys = alternateDist;
                    v.edellinen = u;
                    q.add(v);
                }
            }
        }
    }

    public int lyhyinPolku(String loppu) {
        if (!verkko.containsKey(loppu)) {

            return -1;
        }

        return verkko.get(loppu).etaisyys;
    }

}