package sprint6.tasks.K2

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

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

fun main() {
    val buffer = BufferedReader(InputStreamReader(System.`in`))
    val text = buffer.readText()
    val tokenizer = StringTokenizer(text, " \n\r")
    val vertexCount = tokenizer.nextToken().toInt()
    val edgeCount = tokenizer.nextToken().toInt()
    //Список смежности
    vertexes = Array(vertexCount + 1) { mutableMapOf() }
    //Матрица результатов
    matrix = Array(vertexCount + 1) {
        Array(vertexCount + 1) { Int.MAX_VALUE }
    }

    //Заполнение списка смежности
    repeat(edgeCount) {
        //Считывание строки
        val vertex = tokenizer.nextToken().toInt()
        val toVertex = tokenizer.nextToken().toInt()
        val size = tokenizer.nextToken().toInt()
        //Получение веса ребра между вершинами
        val curSize = vertexes[vertex][toVertex]
        //Если оно не указано или его вес больше считанного -- запомнить
        if (curSize == null || curSize > size) {
            //Т.к. граф неориентированный, каждое ребро ведёт в 2 стороны. Ну или есть 2 ребра в каждую сторону с одинаковым весом
            vertexes[vertex][toVertex] = size
            vertexes[toVertex][vertex] = size
        }
    }
    // Заполнение результата
    matrix.indices.forEach { vertex ->
        if (vertex == 0) return@forEach
        //Расстояние рассчитывается построчно
        //Т.е. для каждой строки применяется алгоритм Дейкстры
        //Массив признаков посещённости
        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].let { if (it != Int.MAX_VALUE) it else -1 }} ")
           appendLine()
        }
    }.let(::print)
}

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

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