Разбор добавил Виталий Павленко

Сформируем из данной нам матрицы тройки чисел \(\langle i, j, a_{ij}\rangle\), где \(a_{ij}\) -- длина кратчайшего пути из \(i\) в \(j\), если он существует. Полученные тройки отсортируем по неубыванию по третьему элементу.
Переберём отсортированный массив. Пусть сейчас мы просматриваем какую-либо тройку. Если существует такая вершина \(k\), что \(a_{ik}+a_{kj}\)<\(a_{ij}\), то ругаемся на некорректные входные данные. Иначе посмотрим, обязаны ли мы добавить в граф, который мы строим, ребро \((i, j)\). Если не существует такого \(k\), что \(a_{ik}+a_{kj}=a_{ij}\), то, очевидно, обязаны. Если же такое \(k\) существует, то мы сохраняем \(a_{ij}\) в массив лишних рёбер -- если после перебора всех троек в нашем отстроенном графе будет недоставать рёбер, то мы доберём их оттуда. Таким образом и получаем ответ.
Вообще говоря, тройки, видимо, сортировать вовсе незачем. Однако удобно представлять, что мы перебираем отсортированные тройки, для понимания логики алгоритма.