import java.io.*;
import java.util.Scanner;


public class floyd {
    private static int[][] adjMatrix;
    private static int[][] pMatrix;
    private static final String OUTPUT_FILE = "output.txt";

    public static void main(String[] args) throws IOException {
        if (args.length != 1) {
            System.err.println("Usage: java Floyd <graph-file>");
            return;
        }

        try (Scanner scanner = new Scanner(new BufferedReader(new FileReader(args[0])))) {
            createFile();

            int problemCount = 0;

            while (scanner.hasNextLine()) {
                String line = scanner.nextLine();

                if (line.startsWith("Problem")) {
                    problemCount++;
                    int n = extractNumberOfVertices(line);

                    if (n < 5 || n > 10) {
                        throw new IllegalArgumentException("Invalid number of vertices.");
                    }

                    // Read adjacency matrix for the current problem
                    initializeMatrices(n, scanner);

                    // Compute shortest paths and print results
                    calculateShortestPaths();
                    printResult(problemCount, n);
                }
            }
        }
    }

    private static void createFile() throws FileNotFoundException {
        PrintWriter writer = new PrintWriter(OUTPUT_FILE);
        writer.close();
    }

    private static int extractNumberOfVertices(String line) {
        // Extracts the number of vertices from the line
        String[] parts = line.split("n = ");
        return Integer.parseInt(parts[1].trim());
    }

    private static void initializeMatrices(int n, Scanner scanner) {
        adjMatrix = new int[n][n];
        pMatrix = new int[n][n];
        
        // Initialize matrices
        for (int i = 0; i < n; i++) {
            String[] values = scanner.nextLine().trim().split("\\s+");
            for (int j = 0; j < n; j++) {
                if (values[j].equals("INF")) {
                    adjMatrix[i][j] = Integer.MAX_VALUE;
                    // No direct path, set pMatrix to -1
                    pMatrix[i][j] = -1;
                } else {
                    int weight = Integer.parseInt(values[j]);
                    adjMatrix[i][j] = weight;
                    // Set pMatrix[i][j] according to whether there is a direct path from i to j
                    if (weight != Integer.MAX_VALUE && i != j) {
                        pMatrix[i][j] = j; // Direct path from i to j, so set pMatrix[i][j] to j
                    } else {
                        pMatrix[i][j] = 0; // No direct path from i to j
                    }
                }
            }
        }
    }
    
    private static void calculateShortestPaths() {
        int n = adjMatrix.length;
        
        // Floyd-Warshall algorithm
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (adjMatrix[i][k] != Integer.MAX_VALUE && adjMatrix[k][j] != Integer.MAX_VALUE) {
                        long newDistance = (long) adjMatrix[i][k] + adjMatrix[k][j];
                        if (newDistance < adjMatrix[i][j]) {
                            adjMatrix[i][j] = (int) newDistance;
                            // Update pMatrix[i][j] to reflect the shortest path from i to j via k
                            pMatrix[i][j] = pMatrix[i][k];
                        }
                    }
                }
            }
        }
    }
    
    
    private static void printResult(int problemCount, int n) throws FileNotFoundException, IOException {
        try (PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(OUTPUT_FILE, true)))) {
            out.println("Problem" + problemCount + ": n = " + n);
            out.println("Pmatrix:");
    
            // Output the pMatrix for the problem
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j) {
                        out.print("0 ");
                    } else {
                        // Print the number of the node just before destination on the shortest path
                        out.print((pMatrix[i][j] != -1 ? (pMatrix[i][j] + 1) : "-") + " ");
                    }
                }
                out.println();
            }
    
            out.println();
    
            // Output shortest paths for each city to all other cities
            for (int source = 0; source < n; source++) {
                out.println("V" + (source + 1) + "-Vj: shortest path and length");
                for (int dest = 0; dest < n; dest++) {
                    // Get the shortest path and distance between the source and destination
                    String path = getShortestPath(source, dest);
                    int distance = adjMatrix[source][dest];
                    out.println(path + ": " + distance);
                }
                out.println();
            }
            out.println(); // Separate problems visually
        }
    }
        
    

    private static String getShortestPath(int source, int dest) {
        if (adjMatrix[source][dest] == Integer.MAX_VALUE) {
            return "No path";
        }
    
        StringBuilder path = new StringBuilder("V" + (source + 1));
        int next = source;
        // Traverse from source to destination using Pmatrix to construct the path
        while (next != dest) {
            next = pMatrix[next][dest];
            if(next == -1) break; // Break if there’s no valid next step (should not happen in a correctly initialized Pmatrix)
            path.append(" V").append(next + 1);
        }
    
        return path.toString();
    }
    

    private static void appendToFile(String output) throws FileNotFoundException {
        try (PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(OUTPUT_FILE, true)))) {
            out.print(output);
        } catch (IOException ex) {
            System.err.println("An error occurred while writing to the file: " + ex.getMessage());
        }
    }
} The logic of Pmatrix should be such that if there is a direct path form the source node to the destination node and self then it should be represented by 0. If there is no direct path from the source node to the destination node then it should find the shortest path between them and print the node which is just before the destination node on the shortest path from source node to destination node