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

public class floyd {
    private static int[][] adjMatrix;
    private static int[][] pMatrix;
    private static final String OUTPUT_FILE = "output.txt";
    private static ArrayList<Integer> path = new ArrayList<>();

    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();

            while (scanner.hasNextLine()) {
                String line = scanner.nextLine();
                if (line.startsWith("Problem")) {
                    // Extract number of vertices from the line
                    int n = Integer.parseInt(line.split("n = ")[1].trim());
                    if (n < 5 || n > 10) {
                        throw new IllegalArgumentException("Invalid number of vertices.");
                    }

                    // Read and initialize the adjacency matrix for the current problem
                    initializeMatrices(n, scanner);
                    
                    // Compute shortest paths and print results
                    calculateShortestPaths();
                    printResult(n);
                }
            }
        }
    }

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

    private static void initializeMatrices(int n, Scanner scanner) {
        adjMatrix = new int[n][n];
        pMatrix = new int[n][n];

        for (int i = 0; i < n; ++i) {
            if (!scanner.hasNextLine()) {
                throw new IllegalStateException("Expected adjacency matrix row is missing.");
            }
            String[] values = scanner.nextLine().trim().split("\s+");
            for (int j = 0; j < n; ++j) {
                int weight = Integer.parseInt(values[j]);
                adjMatrix[i][j] = weight;
                if (weight < 0 || weight > 10) {
                    throw new IllegalArgumentException("Edge weight must be between 0 and 10.");
                }
                if (i == j) {
                    adjMatrix[i][j] = 0;
                } else if (weight != 0) {
                    pMatrix[i][j] = j;
                }
            }
        }
    }

    private static void calculateShortestPaths() {
        int n = adjMatrix.length;

        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] + adjMatrix[k][j] < adjMatrix[i][j]) {
                        adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
                        pMatrix[i][j] = pMatrix[i][k];
                    }
                }
            }
        }
    }

    private static String getFullPathAsString(int source, int dest) {
        if (adjMatrix[source][dest] == Integer.MAX_VALUE) return "No path";
        StringBuilder pathBuilder = new StringBuilder("V" + (source + 1));
        while (source != dest) {
            source = pMatrix[source][dest];
            pathBuilder.append(" V").append(source + 1);
        }
        return pathBuilder.toString();
    }

    private static void printResult(int n) throws FileNotFoundException {
        StringBuilder builder = new StringBuilder();
    
        for (int source = 0; source < n; ++source) {
            builder.append("Problem").append(source + 1).append(": n = ").append(n).append('\n');
            builder.append("Pmatrix:\n");
    
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    builder.append(formatElement(pMatrix[i][j])).append(" ");
                }
                builder.append("\n");
            }
    
            builder.append("\n");
    
            for (int dest = 0; dest < n; ++dest) {
                if (source != dest) { // Skip self to self paths
                    builder.append("V").append(source + 1).append("-V").append(dest + 1).append(": shortest path and length\n");
                    String pathStr = getFullPathAsString(source, dest);
                    builder.append(pathStr)
                            .append(": ")
                            .append(adjMatrix[source][dest])
                            .append("\n");
                }
            }
    
            builder.append("\n\n"); // Separate problems visually
            appendToFile(builder.toString());
            builder.setLength(0); // Reset builder for next problem
        }
    }

    private static boolean isDirectlyConnected(int from, int to) {
        return pMatrix[from][to] == to && adjMatrix[from][to] > 0;
    }
    
    private static String getShortestPathAsString(int source, int destination) {
        if (adjMatrix[source][destination] == Integer.MAX_VALUE) {
            return "No path";
        }
        int intermediate = pMatrix[source][destination];
        StringBuilder pathBuilder = new StringBuilder();
        pathBuilder.append("V").append(source + 1);
        while (source != destination) {
            pathBuilder.append(" V").append(intermediate + 1);
            source = intermediate;
            intermediate = pMatrix[source][destination];
        }
        return pathBuilder.toString();
    }
    

    private static void buildPath(int current, int destination) {
        path.clear();
        if (current != destination) {
            path.add(current);
            while (pMatrix[current][destination] != destination) {
                current = pMatrix[current][destination];
                path.add(current);
            }
            path.add(destination);
        }
    }

    private static void clearPathList() {
        path.clear();
    }

    private static String formatElement(int element) {
        return "%2d ".formatted(element);
    }

    private static void appendToFile(String string) throws FileNotFoundException {
        try (PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(OUTPUT_FILE, true)))) {
            out.println(string);
        } catch (IOException ex) {
            System.err.println("An error occurred while writing to the file: " + ex.getMessage());
        }
    }
} The program is giving output as Problem1: n = 7
Pmatrix:
 0   1   2   3   4   5   6  
 0   0   2   3   4   5   6  
 0   1   0   3   4   5   6  
 0   1   2   0   4   5   6  
 0   1   2   3   0   5   6  
 0   1   2   3   4   0   6  
 0   1   2   3   4   5   0  

V1-V2: shortest path and length
V1 V2: 6
V1-V3: shortest path and length
V1 V3: 5
V1-V4: shortest path and length
V1 V4: 4
V1-V5: shortest path and length
V1 V5: 6
V1-V6: shortest path and length
V1 V6: 3
V1-V7: shortest path and length
V1 V7: 6



Problem2: n = 7
Pmatrix:
 0   1   2   3   4   5   6  
 0   0   2   3   4   5   6  
 0   1   0   3   4   5   6  
 0   1   2   0   4   5   6  
 0   1   2   3   0   5   6  
 0   1   2   3   4   0   6  
 0   1   2   3   4   5   0  

V2-V1: shortest path and length
V2 V1: 6
V2-V3: shortest path and length
V2 V3: 6
V2-V4: shortest path and length
V2 V4: 4
V2-V5: shortest path and length
V2 V5: 5
V2-V6: shortest path and length
V2 V6: 5
V2-V7: shortest path and length
V2 V7: 3



Problem3: n = 7
Pmatrix:
 0   1   2   3   4   5   6  
 0   0   2   3   4   5   6  
 0   1   0   3   4   5   6  
 0   1   2   0   4   5   6  
 0   1   2   3   0   5   6  
 0   1   2   3   4   0   6  
 0   1   2   3   4   5   0  

V3-V1: shortest path and length
V3 V1: 5
V3-V2: shortest path and length
V3 V2: 6
V3-V4: shortest path and length
V3 V4: 3
V3-V5: shortest path and length
V3 V5: 1
V3-V6: shortest path and length
V3 V6: 4
V3-V7: shortest path and length
V3 V7: 6



Problem4: n = 7
Pmatrix:
 0   1   2   3   4   5   6  
 0   0   2   3   4   5   6  
 0   1   0   3   4   5   6  
 0   1   2   0   4   5   6  
 0   1   2   3   0   5   6  
 0   1   2   3   4   0   6  
 0   1   2   3   4   5   0  

V4-V1: shortest path and length
V4 V1: 4
V4-V2: shortest path and length
V4 V2: 4
V4-V3: shortest path and length
V4 V3: 3
V4-V5: shortest path and length
V4 V5: 4
V4-V6: shortest path and length
V4 V6: 1
V4-V7: shortest path and length
V4 V7: 4



Problem5: n = 7
Pmatrix:
 0   1   2   3   4   5   6  
 0   0   2   3   4   5   6  
 0   1   0   3   4   5   6  
 0   1   2   0   4   5   6  
 0   1   2   3   0   5   6  
 0   1   2   3   4   0   6  
 0   1   2   3   4   5   0  

V5-V1: shortest path and length
V5 V1: 6
V5-V2: shortest path and length
V5 V2: 5
V5-V3: shortest path and length
V5 V3: 1
V5-V4: shortest path and length
V5 V4: 4
V5-V6: shortest path and length
V5 V6: 5
V5-V7: shortest path and length
V5 V7: 5



Problem6: n = 7
Pmatrix:
 0   1   2   3   4   5   6  
 0   0   2   3   4   5   6  
 0   1   0   3   4   5   6  
 0   1   2   0   4   5   6  
 0   1   2   3   0   5   6  
 0   1   2   3   4   0   6  
 0   1   2   3   4   5   0  

V6-V1: shortest path and length
V6 V1: 3
V6-V2: shortest path and length
V6 V2: 5
V6-V3: shortest path and length
V6 V3: 4
V6-V4: shortest path and length
V6 V4: 1
V6-V5: shortest path and length
V6 V5: 5
V6-V7: shortest path and length
V6 V7: 3



Problem7: n = 7
Pmatrix:
 0   1   2   3   4   5   6  
 0   0   2   3   4   5   6  
 0   1   0   3   4   5   6  
 0   1   2   0   4   5   6  
 0   1   2   3   0   5   6  
 0   1   2   3   4   0   6  
 0   1   2   3   4   5   0  

V7-V1: shortest path and length
V7 V1: 6
V7-V2: shortest path and length
V7 V2: 3
V7-V3: shortest path and length
V7 V3: 6
V7-V4: shortest path and length
V7 V4: 4
V7-V5: shortest path and length
V7 V5: 5
V7-V6: shortest path and length
V7 V6: 3



Problem1: n = 6
Pmatrix:
 0   1   2   3   4   5  
 0   0   2   3   4   5  
 0   1   0   3   4   5  
 0   1   2   0   4   5  
 0   1   2   3   0   5  
 0   1   2   3   4   0  

V1-V2: shortest path and length
V1 V2: 1
V1-V3: shortest path and length
V1 V3: 2
V1-V4: shortest path and length
V1 V4: 1
V1-V5: shortest path and length
V1 V5: 3
V1-V6: shortest path and length
V1 V6: 4



Problem2: n = 6
Pmatrix:
 0   1   2   3   4   5  
 0   0   2   3   4   5  
 0   1   0   3   4   5  
 0   1   2   0   4   5  
 0   1   2   3   0   5  
 0   1   2   3   4   0  

V2-V1: shortest path and length
V2 V1: 1
V2-V3: shortest path and length
V2 V3: 3
V2-V4: shortest path and length
V2 V4: 2
V2-V5: shortest path and length
V2 V5: 2
V2-V6: shortest path and length
V2 V6: 3



Problem3: n = 6
Pmatrix:
 0   1   2   3   4   5  
 0   0   2   3   4   5  
 0   1   0   3   4   5  
 0   1   2   0   4   5  
 0   1   2   3   0   5  
 0   1   2   3   4   0  

V3-V1: shortest path and length
V3 V1: 2
V3-V2: shortest path and length
V3 V2: 3
V3-V4: shortest path and length
V3 V4: 3
V3-V5: shortest path and length
V3 V5: 3
V3-V6: shortest path and length
V3 V6: 6



Problem4: n = 6
Pmatrix:
 0   1   2   3   4   5  
 0   0   2   3   4   5  
 0   1   0   3   4   5  
 0   1   2   0   4   5  
 0   1   2   3   0   5  
 0   1   2   3   4   0  

V4-V1: shortest path and length
V4 V1: 1
V4-V2: shortest path and length
V4 V2: 2
V4-V3: shortest path and length
V4 V3: 3
V4-V5: shortest path and length
V4 V5: 3
V4-V6: shortest path and length
V4 V6: 5



Problem5: n = 6
Pmatrix:
 0   1   2   3   4   5  
 0   0   2   3   4   5  
 0   1   0   3   4   5  
 0   1   2   0   4   5  
 0   1   2   3   0   5  
 0   1   2   3   4   0  

V5-V1: shortest path and length
V5 V1: 3
V5-V2: shortest path and length
V5 V2: 2
V5-V3: shortest path and length
V5 V3: 3
V5-V4: shortest path and length
V5 V4: 3
V5-V6: shortest path and length
V5 V6: 5



Problem6: n = 6
Pmatrix:
 0   1   2   3   4   5  
 0   0   2   3   4   5  
 0   1   0   3   4   5  
 0   1   2   0   4   5  
 0   1   2   3   0   5  
 0   1   2   3   4   0  

V6-V1: shortest path and length
V6 V1: 4
V6-V2: shortest path and length
V6 V2: 3
V6-V3: shortest path and length
V6 V3: 6
V6-V4: shortest path and length
V6 V4: 5
V6-V5: shortest path and length
V6 V5: 5

But the expected output is Problem1: n = 7
Pmatrix: 
0  0  0  6  3  0  6  
0  0  5  0  0  4  0  
0  5  0  0  0  0  5  
6  0  0  0  3  0  6  
3  0  0  3  0  3  0  
0  4  0  0  3  0  0  
6  0  5  6  0  0  0 

V1-Vj: shortest path and length
V1 V1: 0
V1 V2: 6
V1 V3: 5
V1 V6 V4: 4
V1 V3 V5: 6
V1 V6: 3
V1 V6 V7: 6

V2-Vj: shortest path and length
V2 V1: 6
V2 V2: 0
V2 V5 V3: 6
V2 V4: 4
V2 V5: 5
V2 V4 V6: 5
V2 V7: 3

V3-Vj: shortest path and length
V3 V1: 5
V3 V5 V2: 6
V3 V3: 0
V3 V4: 3
V3 V5: 1
V3 V6: 4
V3 V5 V7: 6

V4-Vj: shortest path and length
V4 V6 V1: 4
V4 V2: 4
V4 V3: 3
V4 V4: 0
V4 V3 V5: 4
V4 V6: 1
V4 V6 V7: 4

V5-Vj: shortest path and length
V5 V3 V1: 6
V5 V2: 5
V5 V3: 1
V5 V3 V4: 4
V5 V5: 0
V5 V3 V6: 5
V5 V7: 5

V6-Vj: shortest path and length
V6 V1: 3
V6 V4 V2: 5
V6 V3: 4
V6 V4: 1
V6 V3 V5: 5
V6 V6: 0
V6 V7: 3

V7-Vj: shortest path and length
V7 V6 V1: 6
V7 V2: 3
V7 V5 V3: 6
V7 V6 V4: 4
V7 V5: 5
V7 V6: 3
V7 V7: 0

Problem2: n = 6
Pmatrix:
0  0  0  0  2  2  
0  0  1  1  0  0  
0  1  0  1  0  2  
0  1  1  0  0  2  
2  0  0  0  0  2  
2  0  2  2  2  0  

V1-Vj: shortest path and length
V1 V1: 0
V1 V2: 1
V1 V3: 2
V1 V4: 1
V1 V2 V5: 3
V1 V2 V6: 4

V2-Vj: shortest path and length
V2 V1: 1
V2 V2: 0
V2 V1 V3: 3
V2 V1 V4: 2
V2 V5: 2
V2 V6: 3

V3-Vj: shortest path and length
V3 V1: 2
V3 V1 V2: 3
V3 V3: 0
V3 V1 V4: 3
V3 V5: 3
V3 V1 V2 V6: 6

V4-Vj: shortest path and length
V4 V1: 1
V4 V1 V2: 2
V4 V1 V3: 3
V4 V4: 0
V4 V5: 3
V4 V1 V2 V6: 5

V5-Vj: shortest path and length
V5 V2 V1: 3
V5 V2: 2
V5 V3: 3
V5 V4: 3
V5 V5: 0
V5 V2 V6: 5

V6-Vj: shortest path and length
V6 V2 V1: 4
V6 V2: 3
V6 V2 V1 V3: 6
V6 V2 V1 V4: 5
V6 V2 V5: 5
V6 V6: 0

Make necessary changes to the code so as to get the proper matrix representation as there in the expected output.