/*
 * @Author: e2hang 2099307493@qq.com
 * @Date: 2025-12-12 13:49:24
 * @LastEditors: e2hang 2099307493@qq.com
 * @LastEditTime: 2025-12-12 13:50:06
 * @FilePath: \undefinedd:\code\Git-DataStructureAlgorithms\模板\图\Floyd最短路径.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18; // 足够大的无穷（要确保 INF + INF 不溢出）

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    // 输入: n = 顶点数, m = 边数
    // 顶点编号假定为 1..n
    if (!(cin >> n >> m)) return 0;

    // 距离矩阵 d，和 next 矩阵用于路径恢复
    vector<vector<ll>> d(n+1, vector<ll>(n+1, INF));
    vector<vector<int>> nxt(n+1, vector<int>(n+1, -1));

    // 初始化：距离为 INF，自身为0
    for (int i = 1; i <= n; ++i) {
        d[i][i] = 0;
        nxt[i][i] = i; // 可选：表示到自身的下一跳是自己
    }

    // 读边（有向图）。若是无向图，请同时赋值两个方向
    // 若图中可能有多条边，取较小的权重
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        if (w < d[u][v]) {
            d[u][v] = w;
            nxt[u][v] = v; // 初始从 u 到 v 的下一跳是 v
        }
    }

    // Floyd–Warshall 主循环
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            if (d[i][k] == INF) continue; // 剪枝：i->k 不可达就跳过
            for (int j = 1; j <= n; ++j) {
                if (d[k][j] == INF) continue; // 剪枝：k->j 不可达就跳过
                ll through = d[i][k] + d[k][j];
                if (through < d[i][j]) {
                    d[i][j] = through;
                    nxt[i][j] = nxt[i][k]; // 路径恢复：先走 i->k 的第一步
                }
            }
        }
    }

    // 检测负权回路：若任何 d[i][i] < 0 表示存在负环（经过该顶点的路径可以无限变小）
    bool has_negative_cycle = false;
    for (int i = 1; i <= n; ++i) {
        if (d[i][i] < 0) {
            has_negative_cycle = true;
            break;
        }
    }

    // 输出示例（可按需修改）
    if (has_negative_cycle) {
        cout << "Graph contains a negative-weight cycle reachable from some vertices.\n";
        // 竞赛中通常要求你输出并退出或按题意处理
    } else {
        // 示例：输出任意两点间的最短距离矩阵（不可达输出 INF 表示）
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (d[i][j] >= INF/4) cout << "INF";
                else cout << d[i][j];
                if (j < n) cout << ' ';
            }
            cout << '\n';
        }
    }

    // 示例：如何恢复一条具体的最短路径（从 u 到 v）
    auto get_path = [&](int u, int v) -> vector<int> {
        vector<int> path;
        if (nxt[u][v] == -1) return path; // 不可达
        int cur = u;
        path.push_back(cur);
        while (cur != v) {
            cur = nxt[cur][v];
            // 防止无限循环（理论上 nxt 应该使得路径在 n 步内结束）
            if (cur == -1) return vector<int>(); 
            path.push_back(cur);
            if ((int)path.size() > n+5) return vector<int>(); // 保护措施：出现异常则返回空
        }
        return path;
    };

    // （可选）读取查询并输出路径示例：
    // int q; cin >> q; while(q--){ int u,v; cin>>u>>v; auto p=get_path(u,v); ... }

    return 0;
}