[baekjoon] 자바 질문입니다.

import java.util.*;
public class Main {
    static final int INF = 100000;
    static int n_insert;
    static int MAX = 10001;
    static int matrix[][]=new int[MAX][MAX];
    static int sum=0;
    static class GraphType{
        int n;
        int [][]weight=new int [MAX][MAX];
        public GraphType(int n){
            this.n=n;

        }

    }
    public static void init_g(GraphType g){
        for(int i=1;i<=g.n;i++)
            for(int j=1;j<=g.n;j++) {
                if(i==j)
                    g.weight[i][j]=0;
                g.weight[i][j] = INF;
            }
    }

    public static void floyd(GraphType g){
        int i, j, k;

        for (i = 1; i <= g.n; i++)
            for (j = 1; j <= g.n; j++)
                matrix[i][j] = g.weight[i][j];

        for (k = 1; k <= g.n; k++) {
            for (i = 1; i <= g.n; i++)
                for (j = 1; j <= g.n; j++)
                    if (matrix[i][k] + matrix[k][j] < matrix[i][j]) {
                        matrix[i][j] = matrix[i][k] + matrix[k][j];
                    }
        }
        // 가중치 계산 알고리즘
        for (int a = 1; a <= g.n; a++)
        {
            for (int b = 1; b <= g.n; b++)
            {
                if (matrix[a][b] < INF)
                    sum += matrix[a][b];
            }
        }
    }
    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        Main m=new Main();
        int start,end;
        int nvertex,number,edge;
        nvertex=s.nextInt();
        edge=s.nextInt();
        number=s.nextInt();
        
        GraphType g=new GraphType(0);
        g.n=nvertex;
        init_g(g);
        for(int a=1;a<=edge;a++){
            start=s.nextInt();
            end=s.nextInt();

            n_insert(g,start,end,number);
        }

        floyd(g);
        System.out.println(sum/2);

    }
    private static void n_insert(GraphType g, int start, int end, int number) {
        n_insert++;
        if (n_insert==number) // 1인 가중치일경우
            g.weight[start][end] = g.weight[end][start]=1;
        else//나머지```


            g.weight[start][end] = g.weight[end][start]=0;
    }
}

백준 23324 문제입니다. 실행하면 답은 잘 나오는데 백준에 제출하면 런타임 에러 (ArrayIndexOutOfBounds)가 계속 나와서요... 혼자서 해보는데 계속 안되서 어느 부분이 문제인지 조언 구해봅니다...ㅠ