#include "ReadWriter.h"
//string, fstream, iostream, vector, Edge.h - included in ReadWriter.h
#include <algorithm>
#include <climits>


using namespace std;
// write all values
void ReadWriter::writeValues(std::vector<std::vector<int>>& result)
{
    if (!fout.is_open())
        throw std::ios_base::failure("file not open");

    string output;
    int N = result.size();
    for(int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i != j)
            {
                if (result[i][j] == INT_MAX)
                    result[i][j] = -1;
                output = to_string(i) + " " + to_string(j) + " " + to_string(result[i][j]) + "\n";
                fout << output;
            }
        }
    }
}

// Матричное возведение в квадрат с заменой умножения на выбор минимум
void squareMatrix(vector<vector<int>> &A)
{
    int N = A.size();
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(i != j)
            {
                for (int k = 0; k < N; k++)
                {
                    // Если ребра существуют
                    if (A[i][k] < INT_MAX && A[k][j] < INT_MAX)
                        A[i][j] = min(A[i][k] + A[k][j], A[i][j]);
                }
            }
        }
    }
}

// Матричное умножение с заменой умножения на выбор минимума
void multiplyMatrix(vector<vector<int>> &A, vector<vector<int>> &B)
{
    int N = A.size();
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(i != j)
            {
                for (int k = 0; k < N; k++)
                {
                    if (A[i][k] < INT_MAX && B[k][j] < INT_MAX)
                        A[i][j] = min(A[i][k] + B[k][j], A[i][j]);
                }
            }
        }
    }
}

void solve(int N, int M, vector<Edge>& edges, vector<vector<int>>& matrix)
{
    // Создаем матрицу. Отсутствие ребра = INT_MAX
    for(int i = 0; i < N; i++)
        matrix[i] = vector<int>(N, INT_MAX);

    // Переписываем список ребер в матрицу смежности
    for(int i = 0; i < M; i++)
        matrix[edges[i].A][edges[i].B] = edges[i].W;

    // Матрица весов
    vector<vector<int>> W = vector<vector<int>>(matrix);

    // Кол-во ребер содержащихся в кратчайшем пути = степень в которую нужно возвести матрицу весов
    int k = N - 1;
    // Бинарное возведение в степень
    while(k > 0)
    {
        if(k % 2 == 1)
        {
            // Умножаем на матрицу весов - увеличиваем кол-во ребер в кратчайшем пути на одно
            multiplyMatrix(matrix, W);
            k--;
        }
        else
        {
            // Возводим матрицу в квадрат - увеличивая кол-во ребер в кратчайшем пути вдвое
            squareMatrix(matrix);
            k /= 2;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ReadWriter rw;
    //Входные параметры
    //N - количество вершин, M - количество ребер в графе
    int N, M;
    rw.read2Ints(N, M);

    //Вектор ребер, каждое ребро представлено 3-мя числами (А, В, W), где A и B - номера вершин, которые оно соединяет, и W - вес ребра
    //Основной структурой выбран вектор, так как из него проще добавлять и удалять элементы (а такие операции могут понадобиться).
    vector<Edge> edges;
    rw.readEgdes(M, edges);

    vector<vector<int>> result(N);

    //Алгоритм решения задачи
    solve(N, M, edges, result);

    rw.writeValues(result);

    return 0;
}