package sprint6.tasks.K

import java.io.BufferedReader
import java.io.InputStreamReader

lateinit var vertexes: Map<Int, MutableMap<Int, Int>>
lateinit var matrix: Map<Int, Array<Int>>

fun main() {
    val buffer = BufferedReader(InputStreamReader(System.`in`))
    val (vertexCount, edgeCount) = buffer.readLine().split(" ").map { it.toInt() }
    //Список смежности
    vertexes = List(vertexCount) { it + 1 }.associateWith { mutableMapOf() }
    //Матрица результатов
    matrix = List(vertexCount) { it + 1 }
        .associateWith {
            Array(vertexCount + 1) { Int.MAX_VALUE }
        }

    //Заполнение списка смежности
    repeat(edgeCount) {
        //Считывание строки
        val (vertex, toVertex, size) = buffer.readLine().split(" ").map { it.toInt() }
        //Получение веса ребра между вершинами
        val curSize = vertexes[vertex]!![toVertex]
        //Если оно не указано или его вес больше считанного -- запомнить
        if (curSize == null || curSize > size) {
            //Т.к. граф неориентированный, каждое ребро ведёт в 2 стороны. Ну или есть 2 ребра в каждую сторону с одинаковым весом
            vertexes[vertex]!![toVertex] = size
            vertexes[toVertex]!![vertex] = size
        }
    }

    // Заполнение результата
    matrix.forEach { (vertex, _) ->
        //Расстояние рассчитывается построчно
        //Т.е. для каждой строки применяется алгоритм Дейкстры
        //Массив признаков посещённости
        val visited = BooleanArray(vertexCount + 1) { false }
        //Расстоянеи до текущей вершины равно нулю
        matrix[vertex]!![vertex] = 0

        //Функция обновления расстояния
        val relax: (Int, Int) -> Unit = { u, v ->
            val potential = matrix[vertex]!![u] + vertexes[v]!![u]!!
            val cur = matrix[vertex]!![v]
            if (cur > potential) {
                matrix[vertex]!![v] = potential
                matrix[v]!![vertex] = potential
            }
        }

        while (true) {
            // вершина на минимальном расстоянии от текущей. Если такой нет -- выход
            val minDistVertex = getMinDistNotVisited(vertex, visited) ?: break
            //Если ближайшая в бесконечности (нет пути), то выход
            if (matrix[vertex]!![minDistVertex] == Int.MAX_VALUE) break

            visited[minDistVertex] = true
            //Соседи текущей обрабатываемой вершины
            val neighbours = vertexes[minDistVertex]!!.keys
                //Т.к. граф неориентированный, то матрица симметрична относительно главной диаогнали
                //А значит все вершины слева от нулевой длины уже обновлены в минимум в прошлых итерациях построчного перебора матрицы
                .filter { it > vertex }
            for (n in neighbours) {
                relax(minDistVertex, n)
            }
        }
    }

    //формирование ответа
    buildString {
        for (i in 1..vertexCount) {
            for (j in 1..vertexCount)
                append("${matrix[i]!![j].takeIf { it != Int.MAX_VALUE } ?: -1} ")
            appendLine()
        }
    }.let(::print)
}

fun getMinDistNotVisited(forVertex: Int, visited: BooleanArray): Int? {
    var currentMinimum = Int.MAX_VALUE
    var currentMinimumVertex: Int? = null

    for (v in vertexes.keys) {
        if (!visited[v] && matrix[forVertex]!![v] < currentMinimum) {
            currentMinimum = matrix[forVertex]!![v]
            currentMinimumVertex = v
        }
    }
    return currentMinimumVertex
}