Как можно улучшить алгоритм?

Стоит задача разработать алгоритм поиска кратчайших путей от одной заданной вершины ко всем другим в неориентированном графе. Использую алгоритм Дейкстры. Решение подаётся в контексте, где оно прогоняется по N кол-ву тестов. На одном из тестов вылетает MLE (Memory Limit Exceed). Просьба помочь или подсказать как можно улучшить производительность алгоритма. Вот, к слову, он:

        final short INFINITY = Short.MAX_VALUE;
    String[] lines = new BufferedReader(new InputStreamReader(System.in))
            .lines()
            .toArray(String[]::new);
    String[] input = lines[0].split(" ");
    int n = Integer.parseInt(input[0]);
    short[][] matrix = new short[n][n];
    int c = Integer.parseInt(input[3]) - 1;
    for (short[] ints : matrix) {
        Arrays.fill(ints, INFINITY);
    }
    int m = Integer.parseInt(input[1]);
    for (int a = 2; a < (m + 2); a++) {
        int i, j;
        input = lines[a].split(" ");
        i = Integer.parseInt(input[0]) - 1;
        j = Integer.parseInt(input[1]) - 1;
        matrix[i][j] = matrix[j][i] = Short.parseShort(input[2]);
    }
    int[] dist = new int[matrix.length];
    Arrays.fill(dist, INFINITY);
    System.gc();
    dist[c] = 0;
    int sel;
    boolean[] visit = new boolean[matrix.length];
    for (short[] ints : matrix) {
        sel = -1;
        for (int j = 0; j < ints.length; ++j) {
            if (!visit[j] && (sel == -1 || dist[j] < dist[sel])) {
                sel = j;
            }
        }
        if (dist[sel] == INFINITY) {
            break;
        }
        visit[sel] = true;
        for (int j = 0; j < matrix[sel].length; ++j) {
            if (matrix[sel][j] == INFINITY) {
                continue;
            }
            int d = (dist[sel] + matrix[sel][j]);
            if (d < dist[j]) {
                dist[j] = d;
            }
        }
    }
    int[] kk = Arrays.stream(lines[1].split(" ")).mapToInt(Integer::parseInt).toArray();
    Arrays.sort(kk);
    int[] res = new int[kk.length];
    Integer[] indices = new Integer[kk.length];
    for (int i = 0; i < res.length; i++) {
        res[i] = dist[kk[i] - 1];
        indices[i] = i;
    }
    Arrays.sort(indices, Comparator.comparingInt(o -> res[o]));
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < kk.length; i++) {
        sb.append(kk[indices[i]]).append(" ").append(res[indices[i]]).append("\n");
    }
    out.println(sb);

Форматы ввода/вывода: