//#include "Dijkstra.h"
#include <limits.h>
#include <fstream>

std::vector<std::vector<int>> shortest_path_all(const std::vector<std::vector<edge>>& graph) {
    // TODO
    std::vector<std::vector<int>> cost_matrix;
    std::vector<int> v;
    bool ok;
    for (int i = 0; i < graph.size(); i++) {
    	cost_matrix.push_back(v);
    }
    for (int i = 0; i < graph.size(); i++) {
        for (int j = 0; j < graph.size(); j++) {
            if (i == j) {
                cost_matrix[i].push_back(0);
            } else {
            cost_matrix[i].push_back(INT_MAX);
            }
        }
    }
    for (int i = 0; i < graph.size(); i++) {
        for (int j = 0; j < graph[i].size(); j++) {
            cost_matrix[i][graph[i][j].first] = graph[i][j].second;
        }
    }
    
    for (int k = 0; k < graph.size(); k++) {
        int source_node = k;
        cost_matrix[source_node][source_node] = 0;
        do {
            ok = true;
            for (int i = 0; i < graph.size(); i++)
                for (int j = 0; j < graph[i].size(); j++) {
                    if(cost_matrix[source_node][graph[i][j].first] > cost_matrix[source_node][i] + 
                                graph[i][j].second) {
                        cost_matrix[source_node][graph[i][j].first] = cost_matrix[source_node][i] + 
                                graph[i][j].second;
                        ok = false;
                    }
                }
        } while (ok == false);
    }

    return cost_matrix;
}

int main() {

    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int n,m;
    int src, dst, cost;

    scanf("%d%d", &n, &m);

    std::vector<std::vector<edge>> graph;
    std::vector<edge> v;
    for(int i = 0; i < n; i++) {
        graph.push_back(v);
    }

    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &src, &dst, &cost);
        src--;
        dst--;
        graph[src].push_back(std::make_pair(dst, cost));
    }

    std::vector<std::vector<int>> cost_matrix;
    cost_matrix = shortest_path_all(graph);
    for (int i = 0; i < cost_matrix.size(); i++) {
        for (int j = 0; j < cost_matrix.size(); j++) {
            printf("%d ", cost_matrix[i][j]);
        }
        printf("\n");
    }

    return 0;

}