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 step : steps) {
            writer.print("V" + (step + 1) + " ");
        }
    }

    // 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 pathLength = 1;
        for (int at = u; at != v; at = next[at][v]) {
            if (next[at][v] == -1) return new int[0];
            pathLength++;
        }
        int[] path = new int[pathLength];
        int at = u;
        for (int i = 0; i < pathLength; i++) {
            path[i] = at;
            at = next[at][v];
        }
        return path;
    }

    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]; // Correcting the problem ID extraction
                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);
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        if (i != j) {
                            writer.print(problemId + " ");
                            writer.print("V" + (i + 1) + "-V" + (j + 1) + ": shortest path and length\n");
                            if (dist[i][j] == INF) {
                                writer.println("No path");
                            } else {
                                printPath(i, j, next, writer);
                                writer.println(": " + dist[i][j]);
                            }
                        }
                    }
                }
            }
        }
        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 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.