import java.util.*;

class Vertex implements Comparable<Vertex> {
    public final String nombre;
    public Arista[] adj;
    public double minDistancia = Double.POSITIVE_INFINITY;
    public Vertex previo;

    public Vertex(String argNombre){
        nombre = argNombre;
    }

    public String toString() {
        return nombre; }

    public int compareTo(Vertex otro) {
        return Double.compare(minDistancia, otro.minDistancia);
    }
}

class Arista {
    public final Vertex objetivo;

    public Arista(Vertex argObjetivo) {
        objetivo = argObjetivo;
    }
}

class Dijkstra {
    public static void computerutas(Vertex fuente) {
        fuente.minDistancia = 0.;
        PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
        vertexQueue.add(fuente);

        while (!vertexQueue.isEmpty()) {
            Vertex u = vertexQueue.poll();

            // Visit each Arista exiting u
            for (Arista e : u.adj) {
                Vertex v = e.objetivo;
                double distanceThroughU = u.minDistancia;
                if (distanceThroughU < v.minDistancia) {
                    vertexQueue.remove(v);

                    v.minDistancia = distanceThroughU ;
                    v.previo = u;
                    vertexQueue.add(v);
                }
            }
        }
    }

    public static List<Vertex> getShortestPathTo(Vertex objetivo) {
        List<Vertex> ruta = new ArrayList<Vertex>();
        for (Vertex vertex = objetivo; vertex != null; vertex = vertex.previo)
            ruta.add(vertex);

        Collections.reverse(ruta);
        return ruta;
    }

    public static void main(String[] args) {


        // primera ruta es horizontal
                    Vertex A = new Vertex("140");
                    Vertex B = new Vertex("134");
                    Vertex C = new Vertex("Lawrence");
                    Vertex D = new Vertex("100");
                    Vertex E = new Vertex("30");
                    Vertex F = new Vertex("R");
                    Vertex G = new Vertex("Summerhill");
                    Vertex H = new Vertex("Warden");
                    Vertex I = new Vertex("Broadview");

        //la segunda ruta es vertical a R
                    Vertex J = new Vertex("Eglinton");
                    Vertex K = new Vertex("19");
                    Vertex L = new Vertex("Kennedy");
                    Vertex M = new Vertex("Chester");

        //la tercera ruta es vertical a Warden
                    Vertex N = new Vertex("Midland");
                    Vertex O = new Vertex("Yorkdale");
                    Vertex P = new Vertex("Davisville");
                    Vertex Q = new Vertex("Donalds");


        // Aristas
        A.adj = new Edge[]{ new Edge(B) };
                    B.adj = new Edge[]{ new Edge(C) };
                    C.adj = new Edge[]{ new Edge(D) };
                    D.adj = new Edge[]{ new Edge(E) };
                    E.adj = new Edge[]{ new Edge(F) };
                    F.adj = new Edge[]{ new Edge(G) };  //intersection
                    G.adj = new Edge[]{ new Edge(H) };
                    H.adj = new Edge[]{ new Edge(I) };  //intersection
                    I.adj = new Edge[]{ new Edge(I) };

                    J.adj = new Edge[]{ new Edge(J) };
                    K.adj = new Edge[]{ new Edge(F) };
                    L.adj = new Edge[]{ new Edge(F) };
                    M.adj = new Edge[]{ new Edge(M) };

                    N.adj = new Edge[]{ new Edge(N) };
                    O.adj = new Edge[]{ new Edge(N) };
                    P.adj = new Edge[]{ new Edge(O) };
                    Q.adj = new Edge[]{ new Edge(Q) };

        //List<Vertex> ruta = null;
        //ruta = getShortestPathTo(whatever station the user chooses);

        //System.out.println("Ruta: " + ruta);
    }
}