package sprint6.tasks.K

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 heap = MyHeap<Int>(compareBy { matrix[vertex][it] })
        heap.put(vertex)

        //Функция обновления расстояния
        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
                heap.put(v)
            }
        }

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

            visited[minDistVertex] = true
            //Соседи текущей обрабатываемой вершины
            val neighbours = vertexes[minDistVertex].keys

            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)
}

class MyHeap<T>(private val comparator: Comparator<T>) {
    private val _heap: MutableList<T> = mutableListOf()
    val heap: List<T>
        get() = _heap

    fun isNotEmpty() = _heap.isNotEmpty()

    fun put(element: T) {
        _heap.add(element)
        siftUp(_heap.lastIndex)
    }

    fun pop(): T {
        if (_heap.isEmpty()) error("heap is empty")
        _heap.swap(0, _heap.lastIndex)
        return _heap.removeLast().also { siftDown(0) }
    }


    private fun siftDown(idx: Int) {
        val left = idx * 2 + 1
        val right = left + 1

        val toSwap = when {
            left >= _heap.size -> return
            right >= _heap.size || comparator.compare(_heap[right], _heap[left]) > 0 -> left
            else -> right
        }
        if (comparator.compare(_heap[idx], _heap[toSwap]) < 0) return
        _heap.swap(toSwap, idx)
        siftDown(toSwap)
    }

    private fun siftUp(idx: Int) {
        if (idx == 0) return
        val parent = (idx - 1) / 2
        if (comparator.compare(_heap[parent], _heap[idx]) < 0) return
        _heap.swap(parent, idx)
        siftUp(parent)
    }

    private fun MutableList<T>.swap(left: Int, right: Int) {
        val tmp = this[left]
        this[left] = this[right]
        this[right] = tmp
    }
}