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

public class floyd {

    public static final int INF = Integer.MAX_VALUE / 2;

    // Function to reconstruct and print the shortest path from u to v
    private static void printPath(int u, int v, int[][] next, PrintWriter writer) {
        if (next[u][v] == -1) {
            writer.println("No path");
            return;
        }
        int[] steps = reconstructPath(u, v, next);
        for (int i = 0; i < steps.length; i++) {
            writer.print("V" + (steps[i] + 1) + " ");
        }
        writer.println(); // Add a newline after printing the path
    }

    // Helper method to reconstruct the path from u to v
    private static int[] reconstructPath(int u, int v, int[][] next) {
        if (next[u][v] == -1)
            return new int[0];
        int[] path = new int[next.length];
        int pathLength = 0;
        int at = u;
        while (at != v) {
            path[pathLength++] = at;
            at = next[at][v];
        }
        path[pathLength++] = v;
        return Arrays.copyOf(path, pathLength);
    }

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

        String inputFile = args[0];
        Scanner scanner = new Scanner(new File(inputFile));
        PrintWriter writer = new PrintWriter("output.txt");

        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (line.startsWith("Problem") && line.contains("n =")) {
                String problemId = line.split(" ")[0]; // Correctly extract the problem ID
                int n = Integer.parseInt(line.split("n =")[1].trim());

                int[][] dist = new int[n][n];
                int[][] next = new int[n][n];

                for (int i = 0; i < n; i++) {
                    line = scanner.nextLine().trim();
                    String[] parts = line.split("\\s+");
                    for (int j = 0; j < n; j++) {
                        int val = Integer.parseInt(parts[j]);
                        if (val == 0 && i != j) {
                            dist[i][j] = INF;
                        } else {
                            dist[i][j] = val;
                        }
                        next[i][j] = (val == 0 && i != j) ? -1 : j;
                    }
                }

                // 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 (dist[i][k] < INF && dist[k][j] < INF && dist[i][j] > dist[i][k] + dist[k][j]) {
                                dist[i][j] = dist[i][k] + dist[k][j];
                                next[i][j] = next[i][k];
                            }
                        }
                    }
                }

                // Printing paths and their lengths
                writer.println(problemId + ": n = " + n);
                writer.println("Pmatrix:");
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        writer.print(dist[i][j] + " ");
                    }
                    writer.println();
                }
                writer.println(); // Add an extra newline after the Pmatrix

                // Printing shortest paths from each city to all other cities
                for (int i = 0; i < n; i++) {
                    writer.println(problemId + " V" + (i + 1) + "-Vj: shortest path and length");
                    for (int j = 0; j < n; j++) {
                        if (i != j) {
                            printPath(i, j, next, writer);
                            writer.print(": ");
                            if (dist[i][j] == INF) {
                                writer.println("No path");
                            } else {
                                writer.println(dist[i][j]);
                            }
                        }
                    }
                    writer.println(); // Add an extra newline after each city's paths
                }
            }
        }
        scanner.close();
        writer.close();
    }
}


Input is 

Problem1 Amatrix: n = 7
0 6 5 4 6 3 6
6 0 6 4 5 5 3
5 6 0 3 1 4 6
4 4 3 0 4 1 4
6 5 1 4 0 5 5
3 5 4 1 5 0 3
6 3 6 4 5 3 0

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

graphfile.txt is the name of a file that includes input. The linesthat correspond to problem j will contains an integer n (between 5 and 10) that indicates how many cities and n x n adjacency matrix A (that is, the distance between n cities, between 1 to 10), in the next n 
rows. Note that no infinity will appear in the matrix A.

The program is giving output as
 
Problem1: n = 7
Pmatrix:
-1  1  2  3  4  5  6  
0  -1  2  3  4  5  6  
0  1  -1  3  4  5  6  
0  1  2  -1  4  5  6  
0  1  2  3  -1  5  6  
0  1  2  3  4  -1  6  
0  1  2  3  4  5  -1  
Problem1 V1-V2: shortest path and length
V1 V2: 6
Problem1 V1-V3: shortest path and length
V1 V3: 5
Problem1 V1-V4: shortest path and length
V1 V4: 4
Problem1 V1-V5: shortest path and length
V1 V5: 6
Problem1 V1-V6: shortest path and length
V1 V6: 3
Problem1 V1-V7: shortest path and length
V1 V7: 6
Problem1 V2-V1: shortest path and length
V2 V1: 6
Problem1 V2-V3: shortest path and length
V2 V3: 6
Problem1 V2-V4: shortest path and length
V2 V4: 4
Problem1 V2-V5: shortest path and length
V2 V5: 5
Problem1 V2-V6: shortest path and length
V2 V6: 5
Problem1 V2-V7: shortest path and length
V2 V7: 3
Problem1 V3-V1: shortest path and length
V3 V1: 5
Problem1 V3-V2: shortest path and length
V3 V2: 6
Problem1 V3-V4: shortest path and length
V3 V4: 3
Problem1 V3-V5: shortest path and length
V3 V5: 1
Problem1 V3-V6: shortest path and length
V3 V6: 4
Problem1 V3-V7: shortest path and length
V3 V7: 6
Problem1 V4-V1: shortest path and length
V4 V1: 4
Problem1 V4-V2: shortest path and length
V4 V2: 4
Problem1 V4-V3: shortest path and length
V4 V3: 3
Problem1 V4-V5: shortest path and length
V4 V5: 4
Problem1 V4-V6: shortest path and length
V4 V6: 1
Problem1 V4-V7: shortest path and length
V4 V7: 4
Problem1 V5-V1: shortest path and length
V5 V1: 6
Problem1 V5-V2: shortest path and length
V5 V2: 5
Problem1 V5-V3: shortest path and length
V5 V3: 1
Problem1 V5-V4: shortest path and length
V5 V4: 4
Problem1 V5-V6: shortest path and length
V5 V6: 5
Problem1 V5-V7: shortest path and length
V5 V7: 5
Problem1 V6-V1: shortest path and length
V6 V1: 3
Problem1 V6-V2: shortest path and length
V6 V2: 5
Problem1 V6-V3: shortest path and length
V6 V3: 4
Problem1 V6-V4: shortest path and length
V6 V4: 1
Problem1 V6-V5: shortest path and length
V6 V5: 5
Problem1 V6-V7: shortest path and length
V6 V7: 3
Problem1 V7-V1: shortest path and length
V7 V1: 6
Problem1 V7-V2: shortest path and length
V7 V2: 3
Problem1 V7-V3: shortest path and length
V7 V3: 6
Problem1 V7-V4: shortest path and length
V7 V4: 4
Problem1 V7-V5: shortest path and length
V7 V5: 5
Problem1 V7-V6: shortest path and length
V7 V6: 3
Problem2: n = 6
Pmatrix:
-1  1  2  3  4  5  
0  -1  2  3  4  5  
0  1  -1  3  4  5  
0  1  2  -1  4  5  
0  1  2  3  -1  5  
0  1  2  3  4  -1  
Problem2 V1-V2: shortest path and length
V1 V2: 1
Problem2 V1-V3: shortest path and length
V1 V3: 2
Problem2 V1-V4: shortest path and length
V1 V4: 1
Problem2 V1-V5: shortest path and length
V1 V5: 3
Problem2 V1-V6: shortest path and length
V1 V6: 4
Problem2 V2-V1: shortest path and length
V2 V1: 1
Problem2 V2-V3: shortest path and length
V2 V3: 3
Problem2 V2-V4: shortest path and length
V2 V4: 2
Problem2 V2-V5: shortest path and length
V2 V5: 2
Problem2 V2-V6: shortest path and length
V2 V6: 3
Problem2 V3-V1: shortest path and length
V3 V1: 2
Problem2 V3-V2: shortest path and length
V3 V2: 3
Problem2 V3-V4: shortest path and length
V3 V4: 3
Problem2 V3-V5: shortest path and length
V3 V5: 3
Problem2 V3-V6: shortest path and length
V3 V6: 6
Problem2 V4-V1: shortest path and length
V4 V1: 1
Problem2 V4-V2: shortest path and length
V4 V2: 2
Problem2 V4-V3: shortest path and length
V4 V3: 3
Problem2 V4-V5: shortest path and length
V4 V5: 3
Problem2 V4-V6: shortest path and length
V4 V6: 5
Problem2 V5-V1: shortest path and length
V5 V1: 3
Problem2 V5-V2: shortest path and length
V5 V2: 2
Problem2 V5-V3: shortest path and length
V5 V3: 3
Problem2 V5-V4: shortest path and length
V5 V4: 3
Problem2 V5-V6: shortest path and length
V5 V6: 5
Problem2 V6-V1: shortest path and length
V6 V1: 4
Problem2 V6-V2: shortest path and length
V6 V2: 3
Problem2 V6-V3: shortest path and length
V6 V3: 6
Problem2 V6-V4: shortest path and length
V6 V4: 5
Problem2 V6-V5: shortest path and length
V6 V5: 5

which is incorrect. 

The correct and 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 

Output the solution of problem 1 first, then problem 2, and etc. The solution of problem j should start with an integer n (the number cities) and the n x n Pointer Array P (in the next n rows). The shortest paths should then follow, one per line. Output the shortest paths from C1 to all other cities, then C2 to all other cities, and Cn to all other cities. Analyze the expected output and accordingly make modifications to the code to get the expected output