class Graph {
    private static int[][] matrix;
    static int[][] pred;

    private Graph(int n) {
        if (n < 0) {
            System.err.println("Error! No negative graph size!");
        } else {
            matrix = new int[n + 1][n + 1];
            pred = new int[n + 1][n + 1];
            for (int i = 1; i < matrix.length; i++) {
                for (int j = 1; j < matrix.length; j++) {
                    if (i == j) {
                        matrix[i][j] = 0;
                        pred[i][j] = Integer.MAX_VALUE;
                    } else {
                        matrix[i][j] = -1;
                        pred[i][j] = Integer.MAX_VALUE;
                    }
                }
            }
        }
    }

    public static void newMat(int n) {
        new Graph(n);
    }

    public static void debug() {
        System.out.println();
        if (matrix == null) {
            System.err.println("Error! Create a new graph first!");
        } else {
            for (int i = 1; i < matrix.length; i++) {
                for (int j = 1; j < matrix.length; j++) {
                    System.out.print(matrix[i][j] + "  ");
                }
                System.out.println();
            }
            System.out.println();
        }
    }

    public static void add(int source, int target, int dist) {
        if (matrix == null) {
            System.err.println("Error! Create new graph first");
        } else if (dist < 0) {
            System.err.println("Error! Cannot add negative distances!");
        } else if ((source <= 0) || (target <= 0)) {
            System.err.println("Error! Node has to be between" + " 1 and "
                    + (matrix.length - 1));
        } else if (source == target) {
            System.err.println("Error! Distance"
                    + " between same nodes is always zero.");
        } else if (source > matrix.length || target > matrix.length) {
            System.err.println("Error! Nodes too  big for Graph!");
        } else if (hasEdge(source, target)) {
            System.err.println("Error! There is already a connection.");
        } else {
            matrix[source][target] = dist;
        }
    }

    public static void delete(int source, int target) {
        if (matrix == null) {
            System.err.println("Error! Create a new graph first");
        } else if (source == target) {
            System.err.println("Error! Cannot remove if source = target");
        } else if (matrix[source][target] == -1) {
            System.err.println("Error! Nothing to delete");
        } else {
            matrix[source][target] = -1;
        }
    }

    public static void help() {
        System.out.println("' 'q'  terminates the program.");
        System.out.println();
        System.out.println("''n x' creates a new graph with the size x. "
                + "The size has to be bigger than 0.");
        System.out.println();
        System.out.println("'d' displays the graph.");
        System.out.println();
        System.out.println("''a x y z' adds a connection from source x, "
                + "to target y, with length z.");
        System.out.println("    If there is already an connection,"
                + " the program displays an error message.");
        System.out.println();
        System.out.println("'Remove x y' | 'r x y' "
                + "removes a connection between x and y.");
        System.out.println("If there is no connection, "
                + " the program displays an error message.");
    }

    public static void matPrint(int[][] mat) {
        for (int i = 1; i < mat.length; i++) {
            for (int j = 1; j < mat.length; j++) {
                System.out.print(mat[i][j] + "  ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static int[] nearNodes(int[][] mat, int source) {
        int count = 0;
        for (int i = 0; i < mat[source].length; i++) {
            if (mat[source][i] > 0 && mat[source][i] != Integer.MAX_VALUE) {
                count++;
            }
        }
        final int[] result = new int[count];
        count = 0;
        for (int i = 0; i < mat[source].length; i++) {
            if (mat[source][i] > 0 && mat[source][i] != Integer.MAX_VALUE) {
                result[count++] = i;
            }
        }
        return result;
    }

    public static boolean hasEdge(int source, int target) {
        return matrix[source][target] > 0;
    }

    public static boolean isValidEdge(int source, int target, int length) {
        return matrix[source][target] == length;
    }

    public static int getDis(int[][] mat, int source, int target) {
        return mat[source][target];
    }

    public static int[][] dojktrsa(int source, int target) {



        int[] pred = new int[matrix.length];
        boolean[] checked = new boolean[matrix.length];
        int[] length = new int[matrix.length];
        int test1 = 0;
        int[] test = nearNodes(matrix, 1);
        for (int a = 0; a<test.length; a++){
            test1  = test[a];
            length[test1] = getDis(matrix, 1, test1);
            pred[test1] = 1;
        }
        for (int i = 1; i < matrix.length; i++) {
            int x = getShortestNode(i);
            checked[i] = true;

            int[] i1 = nearNodes(matrix, x);
            pred[x] = i;



            for (int z = 0; z < i1.length; z++) {
                int t = i1[z];
                int newlength = getDis(matrix, x, i1[z]);
                System.out.println(newlength + "neue länge");
                int bitebite = getDis(matrix, i, x);
                System.out.println(bitebite + " wie groß ist die");
                if (length[t] != 0) {
                    if ( newlength > length[t]) {
                        System.out.println("mal gucken");
                    } else {
                        length[t] = newlength;
                    }
                } else {
                    length[t] = newlength +bitebite ;

                }
            }
                for (int s = 0; s < length.length; s++) {
                    System.out.print(length[s] + " ");
                    System.out.println(pred[s] + "");

                }
                System.out.println();
            }

        for (int s = 0; s < length.length; s++) {
            System.out.println(length[s]);

        }

        return null;

    }

    public static int getShortestNode(int source) {
        int[] mat = new int[matrix.length];
        for (int i = 1; i < matrix.length; i++) {
            if (i == source) {
                for (int j = 1; j < matrix.length; j++) {
                    if (matrix[i][j] != -1) {
                        mat[j] = matrix[i][j];
                    }
                }
            }
        }
        for (int i = 0; i < mat.length; i++) {
            if (mat[i] == 0) {
                mat[i] = Integer.MAX_VALUE;
            }
        }
        int node = 0;
        int small = mat[0];
        for (int i = 0; i < mat.length; i++) {
            if (mat[i] < small) {
                small = mat[i];
                node = i;
            }
        }
        return node;
    }

}