import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class BellmanFord {
    List<Kaari> kaaret = new ArrayList<>(10000);
    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;
        }
    }

    @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 bellmanFord(String alku, String loppu) {
        HashMap<String, Integer> etaisyys = new HashMap<>(kaaret.size());
        etaisyys.put(alku, 0);
        for (int i = 0; i < kaaret.size(); i++) {
            for (Kaari kaari : kaaret) {
                Integer nyky = etaisyys.getOrDefault(kaari.loppu, 10000000);
                Integer uusi = etaisyys.getOrDefault(kaari.alku, 10000000) + kaari.pituus;
                if (uusi < nyky) {
                    etaisyys.put(kaari.loppu, uusi);
                }
            }
        }
        return etaisyys.getOrDefault(loppu, -1);
    }
}