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;
        }
        StringBuilder path = new StringBuilder("V" + (u + 1));
        while (u != v) {
            u = next[u][v];
            path.append(" V").append(u + 1);
        }
        writer.print(path.toString());
    }

    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(" ")[1]; // Corrected to store the ID correctly
                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++) {
                    for (int j = 0; j < n; j++) {
                        if (i == j) dist[i][j] = 0;
                        else dist[i][j] = INF;
                        next[i][j] = -1;
                    }
                }

                for (int i = 0; i < n; i++) {
                    if (scanner.hasNextLine()) {
                        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) {
                                dist[i][j] = val;
                                next[i][j] = j;
                            }
                        }
                    }
                }

                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];
                            }
                        }
                    }
                }

                writer.println(problemId + ": n = " + n);

                // Printing paths and distances
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        if (i != j && dist[i][j] != INF) {
                            writer.print(problemId + " V" + (i + 1) + "-V" + (j + 1) + ": shortest path and length\n");
                            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 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 Fix the logic wherever needed to get the expected output