import java.util.*;

  class Vertex implements Comparable<Vertex>{
     public final String st;
     public Edge[] edges;
     public double distance = Double.POSITIVE_INFINITY;
     public Vertex previous;
      public Vertex(String argName) { st = argName; }
      public String toString() { return st; }
      public int compareTo(Vertex other)      {
          return Double.compare(distance, other.distance);
      }
    }
 class Edge {
      public final Vertex target;
      public final double weight;
      public Edge(Vertex argTarget, double argWeight){ 
          target = argTarget; weight = argWeight;
      }
  }
  public class DijkastraAlgorithm{
      public static void computePaths(Vertex source){
          source.distance = 0;
          PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>();
          queue.add(source);

          while (!queue.isEmpty()) {
              Vertex vx = queue.poll();

              for (Edge e : vx.edges){
                  Vertex v = e.target;
                  double weight = e.weight;
                  double distanceTo = vx.distance + weight;
                    if (distanceTo < v.distance) {
                        queue.remove(v);

                        v.distance = distanceTo ;
                        v.previous = vx;
                        queue.add(v);

                    }
                }
             }
          }
          public static List<Vertex> getShortestPathTo(Vertex target){
         List<Vertex> path = new ArrayList<Vertex>();
         for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
             path.add(vertex);

         Collections.reverse(path);
         return path;
         }

    public static void main(String[] args){
    Vertex v0 = new Vertex("Delhi");
    Vertex v1 = new Vertex("A");
    Vertex v2 = new Vertex("B");
    Vertex v3 = new Vertex("C");
    Vertex v4= new Vertex("D");
    Vertex v5 = new Vertex("E");
    Vertex v6 = new Vertex("F");
    v0.edges = new Edge[]{ new Edge(v1,  80),
                                 new Edge(v5,  81) };
    v1.edges = new Edge[]{ new Edge(v0,  80),
                                 new Edge(v2,  40),
                                 new Edge(v3, 100) };
    v2.edges = new Edge[]{ new Edge(v1,  40) };
    v3.edges = new Edge[]{ new Edge(v1, 103),
                                 new Edge(v5,  61),
                                 new Edge(v6,  97) };
    v4.edges = new Edge[]{ new Edge(v5, 133) };
    v5.edges = new Edge[]{ new Edge(v0,  88),
                                 new Edge(v3,  62),
                                 new Edge(v4, 134),
                                 new Edge(v6,  92) };
    v6.edges = new Edge[]{ new Edge(v3,  97),
                                 new Edge(v5,  88) };
    Vertex[] vertices = { v0, v1, v2, v3, v4, v5, v6};
    computePaths(v0);
    for (Vertex v : vertices){
        System.out.println("Distance to " + v + ": " + v.distance);
        List<Vertex> path = getShortestPathTo(v);
        System.out.println("Path: " + path);
    }

     }
 }