import java.util.List;
import java.util.LinkedList;
import java.util.Stack;
import java.util.Iterator;
import java.util.ArrayList;
import java.util.Comparator;

interface Infinity {
    final int value = Integer.MAX_VALUE;
}

public class WeightedGraph {
    private final int DEFAULT_SIZE = 5;
    private ArrayList<Vertex> vertices;
    private int numVertices;
    private boolean undirected;
    /**
     * Default Constructor
     */
    public WeightedGraph() {
        vertices = new ArrayList<Vertex>(DEFAULT_SIZE);
        numVertices = 0;
        for( int i = 0; i < DEFAULT_SIZE ; i++ ) vertices.add(null);
        undirected = false;
    } // end constructor
    /**
     * Constructor with parameter
     * @param if undirected is true then the graph is undirected
     */
    public WeightedGraph(boolean undirected) {
        vertices = new ArrayList<Vertex>(DEFAULT_SIZE);
        numVertices = 0;
        for( int i = 0; i < DEFAULT_SIZE ; i++ ) vertices.add(null);
        this.undirected = undirected;
    } // end constructor
    
    /**
     * Constructor with parameters
     * @param size is the number of vertices
     * @param if undirected is true then the graph is undirected
     */
    public WeightedGraph(boolean undirected, int size) {
        vertices = new ArrayList<Vertex>(size);
        for( int i = 0; i < size; i++ ) vertices.set(i,new Vertex(i));
        numVertices = size;
        this.undirected = undirected;
    } // end constructor
    
    /**
     * This adds an edge to the graph
     * @param the edge is from vertex v1 to vertex v2 and vice versa if undirected
     */
    public void addEdge(int v1, int v2, int weight) {
        if( v1 >= vertices.size() ) resize(v1);
        if( vertices.get(v1) == null ) {
            vertices.set(v1,new Vertex(v1));
            numVertices++;
        } // end if
        if( v2 >= vertices.size() ) resize(v2);
        if( vertices.get(v2) == null ) {
            vertices.set(v2,new Vertex(v2));
            numVertices++;
        } // end if
        vertices.get(v1).adjList.add( new Edge(v2,weight) );
        if( undirected ) vertices.get(v2).adjList.add( new Edge(v1,weight) );
    }// end addEdge
    
    /**
     * Calculates all shortest paths from a start vertex
     * @param the start vertex
     */
    public void allShortestPaths(int fromVertex) {
        resetGraph();
        PriorityQueue<Vertex> priorityQ = new BinaryHeap<Vertex>(new DistanceComparator());
        priorityQ.add(vertices.get(fromVertex));
        vertices.get(fromVertex).distance = 0;
        while( !priorityQ.isEmpty() ) {
            Vertex v = priorityQ.removeMin();
            // if v is already on the shortest path skip it
            if( v.marked ) continue;
            // now v is on the shortest path
            v.marked = true;
            for(Edge e : v.adjList ) {
                Vertex w = vertices.get(e.vertex);
                if( w.marked ) continue;
                int weight = e.weight;
                if( w.distance > v.distance + weight ) {
                    w.distance = v.distance + weight;
                    w.previous = v.name;
                    priorityQ.add(w);
                } // end if
            } // end while Itr.hasNext())
        } // end while !priortyQ.isEmpty())
    } // end AllShortestPaths
    /**
     * Finds the shortest path to a particular vertex
     * @return an ArrayList of the vertices on the shortest path
     * and return the weighted length of the path in position 0 of the ArrayList
     */
    public ArrayList<Integer> shortestPathArray(int toVertex) {
        if( !vertices.get(toVertex).marked ) return null;
        if(vertices.get(toVertex).previous == -1 ) {
            ArrayList<Integer> path = new ArrayList<Integer>();
            path.add(toVertex);
            return path;
        } else {
            ArrayList<Integer> path = shortestPathArray(vertices.get(toVertex).previous);
            path.add(toVertex);
            return path;
        }// end if
    } // end shortestPathArray
    
    /**
     * @return the adjacency lists as a String
     */
    public String toString() {
        String out = "Graph (weights are in parenthesis)\n";
        for( int i = 0; i < numVertices; i++ ) {
            out = out + "Vertex " + i + " adjacent vertices: ";
            for( Edge edge : vertices.get(i).adjList ) {
                out = out + edge + " ";
            } // end for
            out = out + '\n';
        } // end for
        return out;
    } // end toString
    
    /**
     * The number of vertices in the graph
     * @return the number of vertices
     */
    public int numberOfVertices() {
        return numVertices;
    }
    
    private void resize(int size) {
        ArrayList<Vertex> temp = vertices;
        vertices = new ArrayList<Vertex>(size+1);
        for( int i = 0; i < temp.size(); i++ ) vertices.add(temp.get(i));
        for( int i = temp.size(); i < size + 1; i++ ) vertices.add(null);
    } // end resize
    
    private void resetGraph() {
        for( int v = 0; v < numVertices; v++ ) {
            vertices.get(v).marked = false;
            vertices.get(v).previous = -1;
            vertices.get(v).distance = Infinity.value;
        } // end for
    } // end resetGraph
    
    private class Edge {
        int vertex;
        int weight;
        
        Edge(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }
        public String toString() {
            return "  " + vertex + " (" + weight + ") ";
        }
    } // end Edge
    
    private class Vertex  {
        int name;
        List<Edge> adjList;
        int distance;
        int previous;
        boolean marked;
        
        Vertex(int name) {
            this.name = name;
            this.distance = Infinity.value;
            this.previous = -1;
            marked = false;
            adjList = new LinkedList<Edge>();
        }
        
        public String toString() {
            return name + " " + distance + "   ";
        }
        
    } // end Vertex
    
    class DistanceComparator implements Comparator<Vertex> {
        public int compare(Vertex v, Vertex w) {
            return v.distance - w.distance;
        } // end compare
    }// end Comparator
    
    
} // end WeightedGraph