import java.util.Scanner;

public class Dijkstra {
    static char[] labels = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' }; // Create labels to show the indexing
                                                                                 // of the array in form of alphabet.
                                                                                 // Since the assignment only ask for
                                                                                 // the 10 nodes, so the label only
                                                                                 // created until the tenth alphabet.

    // Function to print the path from the source to the destination, it is the
    // recursion function, and it will print each path as long as it is available in
    // the path array, it will stop until print the source array
    private static void printPath(int[] path, int destination, char[] labels) {
        // System.out.print("\tShortest path: ");
        if (path[destination] == -1) {
            System.out.print(labels[destination] + " ");
            return;
        } else {
            printPath(path, path[destination], labels);
            System.out.print(labels[destination] + " ");
        }
    }

    // Function to get the vertex (with the minimum distance of the currently
    // vertex) of each vertex or node that did not visited yet, it will return the
    // vertex with the minimum distance of the currently vertex
    private static int getMinimumVertex(boolean[] visited, int[] distance) {
        int minDistance = Integer.MAX_VALUE; // Set the initial minimal distance as the infinite
        int vertex = -1; // If the minimum vertex did not found, then the vertex will be excluded, -1 did
                         // not refer to any indexing array
        for (int i = 0; i < visited.length; i++) {
            // If the vertex did not visited yet and its distance is less than the distance
            // of currently vertex, then update the minDistance and return the vertex
            if (!visited[i] && distance[i] < minDistance) {
                minDistance = distance[i];
                vertex = i;
            }
        }
        return vertex;
    }

    public static void runDijkstra(int[][] graph, int source, int destination, char[] labels) {
        int graphSize = graph.length; // since the graph size take the indexing of the first array, it is also equal
                                      // to the amount of the node of the graph
        boolean[] visited = new boolean[graphSize]; // Create a new array that store the list of not visided vertices of
                                                    // the graph. The element of the array did not declared, and so the
                                                    // value of all of the array element is false, means all of the
                                                    // vertices did not visited yet. It will change when the first
                                                    // iteration below start.
        int[] distance = new int[graphSize]; // Create a new array to store the distance
        int[] path = new int[graphSize]; // Create a new array to store the path

        for (int i = 0; i < graphSize; i++) {
            distance[i] = Integer.MAX_VALUE; // Assign the distance of each vertex from the source as the infinite value
            path[i] = -1; // Assign the path of each vertex from the source as unknown, cause initially
                          // when the dijkstra algorithm start, the path is still unknown. -1 set as the
                          // senital value that did not refer to any path of the path array, since -1 did
                          // not include as the array indexing.
        }

        distance[source] = 0; // Update the distance of the source vertices to itself, and it is 0

        // The main loop to find the shortest path
        for (int i = 0; i < graphSize; i++) { // graphSize - 1
            int vertex = getMinimumVertex(visited, distance); // It will start of the element of visited array that its
                                                              // index equal to the source
            visited[vertex] = true; // Update the element of the visited array that has been visited

            // This loop will update the path and the distance of the source to the adjacent
            // vertices for each iteration
            for (int j = 0; j < graphSize; j++) {
                int edgeWeight = graph[vertex][j];
                if (edgeWeight > 0 &&
                        !visited[j] &&
                        distance[vertex] != Integer.MAX_VALUE &&
                        distance[vertex] + edgeWeight < distance[j]) {
                    distance[j] = distance[vertex] + edgeWeight;
                    path[j] = vertex;
                }
            }
        }

        System.out.print("\tShortest path: ");
        printPath(path, destination, labels); // Call the printPath() to print the path
        System.out.println("\n\tShortest distance: " + distance[destination]); // Print the distance
    }

    public static void main(String[] args) {
        Scanner scannerInt = new Scanner(System.in);
        Scanner scannerAlphabet = new Scanner(System.in);

        // Ask user to input the number of the nodes of the graph
        // and store it to the numNodes variable as the integer
        System.out.print("Enter the number of nodes of the graph: ");
        int numNodes = scannerInt.nextInt();

        int[][] graph = new int[numNodes][numNodes]; // Create a new 2D array that contain the information of the graph

        System.out.println("\nInput the weight sequentially and seperate it by the space sign.\n");
        for (int i = 0; i < numNodes; i++) { // In this iteration, the user will be asked to input the weight of each
                                             // node to another node
            System.out.print("\tEnter the weight from node " + labels[i] + " to node ");
            for (int k = 0; k < numNodes; k++) { // Print another node beside currently node and with the comma sign
                                                 // that seperate them
                if (k != i) {
                    System.out.print(labels[k]);
                }
                if (k != i && (k != numNodes - 1)) {
                    if (i == numNodes - 1) {
                        if (k != numNodes - 2) {
                            System.out.print(", ");
                        }
                    } else {
                        System.out.print(", ");
                    }
                }
            }
            System.out.print(": ");

            // Assign the user inputted data to the element of 2D array
            for (int j = 0; j < numNodes; j++) {
                if (i == j) {
                    graph[i][j] = 0;
                } else {
                    graph[i][j] = scannerInt.nextInt();
                }
            }
        }

        // Ask user to input the source in alphabet form
        System.out.print("\nEnter the source node (A, or B, or C, and so on): ");
        char inputChar = scannerAlphabet.nextLine().toUpperCase().charAt(0);
        int source = inputChar - 'A'; // Unicode of A is 66, by write it in form of singular char and assign it in
                                      // integer data type, it will read as the the unicode that corresponding for it.
        System.out.println("");

        // Call the dijkstra() function for each destination that availabe of the nodes
        for (int i = 0; i < graph.length; i++) {
            int destination = i;
            System.out.println("\tDestination: " + labels[destination]);
            runDijkstra(graph, source, destination, labels);
            if (destination < graph.length - 1) // Print the new line after one destination already printed, except for
                                                // the last estination
                System.out.println("");
        }

        scannerAlphabet.close();
        scannerInt.close();
    }
}