import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;


class Vertex<E extends Comparable<E>> implements Comparable<Vertex<E>>{
    private E data;
    private double minDistance;
    private Vertex predecessor;

    public Vertex(E data){
        this.data = data;
        this.minDistance = Double.MAX_VALUE;
        this.predecessor = null;
    }

    public boolean hasPredecessor(){
        return this.predecessor != null;
    }

    public double getMinDistance() {
        return minDistance;
    }

    public void setMinDistance(double minDistance) {
        this.minDistance = minDistance;
    }

    public Vertex<E> getPredecessor() {
        return predecessor;
    }

    public void setPredecessor(Vertex predecessor) {
        this.predecessor = predecessor;
    }

    public E getData() {
        return data;
    }

    public void setData(E data) {
        this.data = data;
    }

    @Override
    public int compareTo(Vertex<E> v) {
        return Double.compare(minDistance, v.getMinDistance());
    }

    @Override
    public int hashCode() {
        int hash = 3;
        hash = 29 * hash + Objects.hashCode(this.data);
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Vertex<E> other = (Vertex<E>) obj;
        if (!this.data.equals(other.data)) {
            return false;
        }
        return true;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("Vertex with data: ")
                .append(this.data)
                .append(" minDist: ")
                .append(this.minDistance)
                .append(" Pred: ")
                .append(this.predecessor.getData());
        return sb.toString();
    }

}

class Edge<E extends Comparable<E>>{
    private Vertex<E> source;
    private Vertex<E> destination;
    private double weight;

    public Edge(Vertex<E> source, Vertex<E> destination, double weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }

    public Vertex<E> getSource() {
        return source;
    }

    public void setSource(Vertex<E> source) {
        this.source = source;
    }

    public Vertex<E> getDestination() {
        return destination;
    }

    public void setDestination(Vertex<E> destination) {
        this.destination = destination;
    }

    public double getWeight() {
        return weight;
    }

    public void setWeight(double weight) {
        this.weight = weight;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("Edge from: ")
                .append(this.source.toString())
                .append("\nTo: ")
                .append(this.destination.toString())
                .append("\nWith weight: " + this.weight);
        return sb.toString();
    }



}
class Graph<E extends Comparable<E>>{

    List<Vertex<E>> vertices;
    List<Edge<E>> edges;
    Map<E,Integer> indexes; // E( name of the vertex) -> Integer (position in list vertices)

    public Graph(){
        vertices = new ArrayList<>();
        edges = new ArrayList<>();
        indexes = new HashMap<>();
    }

    public void addVertex(E data){
        Vertex<E> vertex = new Vertex<>(data);
        vertices.add(vertex);
        int index = vertices.size() - 1;
        indexes.put(data, index);
    }

    public Vertex<E> getVertex(E data){
       return vertices.get(indexes.get(data));
    }

    private boolean addEdge(Vertex<E> source,Vertex<E> destination,double weight){
        return edges.add(new Edge<E>(source,destination,weight));
    }

    public boolean addDirectedEdge(E source,E destination,double weight){
        Vertex<E> s = vertices.get(indexes.get(source));
        Vertex<E> d = vertices.get(indexes.get(destination));
        return addEdge(s,d,weight);
    }
    public boolean addUndirectedEdge(E source,E destination,double weight){
        Vertex<E> s = vertices.get(indexes.get(source));
        Vertex<E> d = vertices.get(indexes.get(destination));

        return addEdge(s,d,weight) && addEdge(d,s,weight);
    }

    public List<Vertex<E>> getVertices(){
        return this.vertices;
    }

    public List<Edge<E>> getEdges(){
        return this.edges;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        for (Vertex<E> v : this.getVertices()){
            sb.append(v.toString() + "\n");
        }
        return sb.toString();
    }

    public double getMinDistanceBetweenDijkstra(E start,E end){
        Vertex<E> source = vertices.get(indexes.get(start));
        Vertex<E> destination = vertices.get(indexes.get(end));
        Dijkstra<E> dijkstra = new Dijkstra<>();

        dijkstra.run(this, source);

        return destination.getMinDistance();
    }

    public double getMinDistanceBetweenBellmanFord(E start,E end){
        Vertex<E> source = vertices.get(indexes.get(start));
        Vertex<E> destination = vertices.get(indexes.get(end));

        BellmanFord<E> bellmanFord = new BellmanFord<>();

        if (bellmanFord.run(this, source))
            return destination.getMinDistance();

        else{
            return -1;
        }
    }

    /*
    MatrixPair class
    */
    ////////////////////////////////////////////////////////////////////////////
    class Matrix{
        double[][] adjMatrix;
        Integer[][] parrentMatrix;

        public Matrix(double[][] adjMatrix, Integer[][] parrentMatrix) {
            this.adjMatrix = adjMatrix;
            this.parrentMatrix = parrentMatrix;
        }

        public double[][] getAdjMatrix() {
            return adjMatrix;
        }

        public Integer[][] getParrentMatrix() {
            return parrentMatrix;
        }

        public List<Integer> getPathBetween(int source,int destination){
            int start = source - 1;
            int finish = destination - 1;
            List<Integer> path = new ArrayList<>();
            while(parrentMatrix[start][finish] != start){
                path.add(parrentMatrix[start][finish] + 1);
                finish = parrentMatrix[start][finish];
            }
            path.add(parrentMatrix[start][finish] + 1);
            Collections.reverse(path);
            return path;
        }

        public double getDistanceBetween(int source,int destination){
            int start = source - 1;
            int finish = destination - 1;
            return this.adjMatrix[start][finish];
        }
    }
    ////////////////////////////////////////////////////////////////////////////

    public Matrix getMinDistanceFloydWarshall(double[][] adjMat){
        int N = adjMat.length;

        Integer[][] parentMatrix = new Integer[N][N];

        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                parentMatrix[i][j] = null;
            }
        }

        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (adjMat[i][j] != Double.MAX_VALUE / 2 && adjMat[i][j] != 0.0){
                    parentMatrix[i][j] = i;
                }
            }
        }


        for(int k = 0; k < N; ++k) {
            for(int i = 0; i < N; ++i) {
                for(int j = 0; j < N; ++j) {
                    if ( adjMat[i][k] + adjMat[k][j] < adjMat[i][j] ){
                        parentMatrix[i][j] = parentMatrix[k][j];
                    }
                    adjMat[i][j] = Math.min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]);
                }
            }
        }

        return new Matrix(adjMat,parentMatrix);
    }


    public double[][] getAdjMatrix(){
        int N = vertices.size();
        double[][] matrix = new double[N][N];
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                if (i == j)
                    continue;
                else{
                    matrix[i][j] = Double.MAX_VALUE / 2.0;
                }
            }
        }
        List<Edge<E>> egdes = this.getEdges();
        for (Edge<E> e : edges){
            matrix[indexes.get(e.getSource().getData())][indexes.get(e.getDestination().getData())] = e.getWeight();
        }
        return matrix;
    }
}

class Dijkstra<E extends Comparable<E>>{

    public Dijkstra(){
    }

    private Hashtable<Vertex<E>, List<Edge<E> > > makeHashtable(Graph<E> graph){
            Hashtable<Vertex<E>, List<Edge<E> > > table = new Hashtable<>();
            List<Edge<E>> lst;
            for (Vertex<E> v : graph.getVertices()){
                lst = new LinkedList<>();
                table.put(v,lst);
            }

            for (Edge<E> e : graph.getEdges()){
                table.get(e.getSource()).add(e);
            }

            return table;
        }
    public void run(Graph<E> graph, Vertex<E> startVertex){

        if (graph == null || startVertex == null)
        return;

        for (Vertex<E> v : graph.getVertices()){
            v.setMinDistance(Double.MIN_VALUE);
            v.setPredecessor(null);
        }

        startVertex.setMinDistance(Double.MAX_VALUE);
        PriorityQueue<Vertex<E>> queue = new PriorityQueue<>(graph.getVertices());
        Hashtable<Vertex<E>, List<Edge<E>>> table = makeHashtable(graph);

        while (!queue.isEmpty()){
            Vertex<E> u = queue.poll();

            for (Edge<E> e : table.get(u)){
                Vertex<E> v = e.getDestination();
                if (v.getMinDistance() < Math.min(u.getMinDistance(),e.getWeight())){
                    v.setMinDistance(Math.min(u.getMinDistance(),e.getWeight()));
                    v.setPredecessor(u);
                    queue.add(v);
                }
            }
        }

    }

}

class BellmanFord<E extends Comparable<E>>{

    private void relax(Edge<E> edge){
        if (edge.getDestination().getMinDistance() < Math.min(edge.getSource().getMinDistance(),edge.getWeight())){
            edge.getDestination().setMinDistance(Math.min(edge.getSource().getMinDistance(),edge.getWeight()));
            edge.getDestination().setPredecessor(edge.getSource());
        }
    }
    public boolean run(Graph<E> graph, Vertex<E> startVertex){
        if (graph == null || startVertex == null)
        return false;

        for (Vertex<E> v : graph.getVertices()){
            v.setMinDistance(Double.MIN_VALUE);
            v.setPredecessor(null);
        }

        startVertex.setMinDistance(Double.MAX_VALUE);

        for (int i = 0; i < graph.getVertices().size(); i++){
            for (Edge<E> edge : graph.getEdges()){
                relax(edge);
            }
        }

        for (Edge<E> edge : graph.getEdges()){
            if (edge.getDestination().getMinDistance() < Math.min(edge.getSource().getMinDistance(),edge.getWeight())){
                return false;
            }
        }

        return true;
    }
}

public class Main{

 public static void main(String[] args){
     Graph<Integer> g = new Graph<>();
     double[][] d = new double[5][5];

     d[0][0] = 0;
     d[0][1] = 3;
     d[0][2] = 8;
     d[0][3] = Double.MAX_VALUE / 2;
     d[0][4] = -4;

     d[1][0] = Double.MAX_VALUE / 2;;
     d[1][1] = 0;
     d[1][2] = Double.MAX_VALUE / 2;;
     d[1][3] = 1;
     d[1][4] = 7;

     d[2][0] = Double.MAX_VALUE / 2;;
     d[2][1] = 4;
     d[2][2] = 0;
     d[2][3] = Double.MAX_VALUE / 2;;
     d[2][4] = Double.MAX_VALUE / 2;;

     d[3][0] = 2;
     d[3][1] = Double.MAX_VALUE / 2;;
     d[3][2] = -5;
     d[3][3] = 0;
     d[3][4] = Double.MAX_VALUE / 2;;

     d[4][0] = Double.MAX_VALUE / 2;;
     d[4][1] = Double.MAX_VALUE / 2;;
     d[4][2] = Double.MAX_VALUE / 2;;
     d[4][3] = 6;
     d[4][4] = 0;


     System.out.println(g.getMinDistanceFloydWarshall(d).getPathBetween(1, 2));
     System.out.println(g.getMinDistanceFloydWarshall(d).getDistanceBetween(1, 2));


     for (int i = 1; i  <= 5; i++){
         g.addVertex(i);
     }

     g.addDirectedEdge(1, 2, 3);
     g.addDirectedEdge(1, 5, -4);
     g.addDirectedEdge(1, 3, 8);

     g.addDirectedEdge(2, 4, 1);
     g.addDirectedEdge(2, 5, 7);

     g.addDirectedEdge(3, 2, 4);

     g.addDirectedEdge(4, 1, 2);
     g.addDirectedEdge(4, 3, -5);

     g.addDirectedEdge(5, 4, 6);

     System.out.println(g.getMinDistanceFloydWarshall(g.getAdjMatrix()).getPathBetween(1, 2));
     System.out.println(g.getMinDistanceFloydWarshall(g.getAdjMatrix()).getDistanceBetween(1, 2));


    }

}