/**
* author: longvu
* created: 04/20/24 02:12:34
**/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
const int INF = 1e18;
const int nax = (int)(501);
const int mod = 1e9 + 7;
template<class X, class Y>
bool maximize(X& x, const Y y) {
if (y > x) {x = y; return true;}
return false;
}
template<class X, class Y>
bool minimize(X& x, const Y y) {
if (y < x) {x = y; return true;}
return false;
}
struct Floyd {
int n, sh_path[nax][nax], next[nax][nax];
Floyd(int n) : n(n) {
memset(next, -1, sizeof next);
memset(sh_path, 0x3f, sizeof sh_path);
for (int i = 1; i <= n; ++i) {
sh_path[i][i] = 0;
}
}
void add_edge(int u, int v, int val) {
minimize(sh_path[u][v], val);
next[u][v] = v;
}
void solve() {
for (int e = 1; e <= n; ++e) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (sh_path[i][e] == INF || sh_path[e][j] == INF) {
continue;
}
if (sh_path[i][e] + sh_path[e][j] < sh_path[i][j]) {
sh_path[i][j] = sh_path[i][e] + sh_path[e][j];
next[i][j] = next[i][e];
}
}
}
for (int i = 1; i <= e; ++i) {
for (int j = 1; j <= e; ++j) {
cout << (sh_path[i][j] >= INF ? -1 : sh_path[i][j]) << " ";
}
cout << '\n';
}
}
}
vector<int> find_path(int u, int v) {
vector<int> path = {u};
if (next[u][v] == -1) {
return {};
}
while (u != v) {
u = next[u][v];
path.push_back(u);
}
return path;
}
};
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
Floyd floyd(n);
for (int i = 1; i <= m; ++i) {
int u, v, c;
cin >> u >> v >> c;
floyd.add_edge(u, v, c);
}
floyd.solve();
return 0;
}
LyoqCiAqICAgIGF1dGhvcjogIGxvbmd2dQogKiAgICBjcmVhdGVkOiAwNC8yMC8yNCAwMjoxMjozNAoqKi8KI2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGludCBsb25nIGxvbmcKI2RlZmluZSBzeih4KSAoKGludCl4LnNpemUoKSkKI2RlZmluZSBhbGwoeCkgKHgpLmJlZ2luKCksICh4KS5lbmQoKQpjb25zdCBpbnQgSU5GID0gMWUxODsKY29uc3QgaW50IG5heCA9IChpbnQpKDUwMSk7CmNvbnN0IGludCBtb2QgPSAxZTkgKyA3OwoKdGVtcGxhdGU8Y2xhc3MgWCwgY2xhc3MgWT4KYm9vbCBtYXhpbWl6ZShYJiB4LCBjb25zdCBZIHkpIHsKICAgIGlmICh5ID4geCkge3ggPSB5OyByZXR1cm4gdHJ1ZTt9CiAgICByZXR1cm4gZmFsc2U7Cn0KdGVtcGxhdGU8Y2xhc3MgWCwgY2xhc3MgWT4KYm9vbCBtaW5pbWl6ZShYJiB4LCBjb25zdCBZIHkpIHsKICAgIGlmICh5IDwgeCkge3ggPSB5OyByZXR1cm4gdHJ1ZTt9CiAgICByZXR1cm4gZmFsc2U7Cn0KCnN0cnVjdCBGbG95ZCB7CiAgICBpbnQgbiwgc2hfcGF0aFtuYXhdW25heF0sIG5leHRbbmF4XVtuYXhdOwogICAgRmxveWQoaW50IG4pIDogbihuKSB7CiAgICAgICAgbWVtc2V0KG5leHQsIC0xLCBzaXplb2YgbmV4dCk7CiAgICAgICAgbWVtc2V0KHNoX3BhdGgsIDB4M2YsIHNpemVvZiBzaF9wYXRoKTsKICAgICAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyArK2kpIHsKICAgICAgICAgICAgc2hfcGF0aFtpXVtpXSA9IDA7CiAgICAgICAgfQogICAgfQoKICAgIHZvaWQgYWRkX2VkZ2UoaW50IHUsIGludCB2LCBpbnQgdmFsKSB7CiAgICAgICAgbWluaW1pemUoc2hfcGF0aFt1XVt2XSwgdmFsKTsKICAgICAgICBuZXh0W3VdW3ZdID0gdjsKICAgIH0KCiAgICB2b2lkIHNvbHZlKCkgewogICAgICAgIGZvciAoaW50IGUgPSAxOyBlIDw9IG47ICsrZSkgewogICAgICAgICAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyArK2kpIHsKICAgICAgICAgICAgICAgIGZvciAoaW50IGogPSAxOyBqICA8PSBuOyArK2opIHsKICAgICAgICAgICAgICAgICAgICBpZiAoc2hfcGF0aFtpXVtlXSA9PSBJTkYgfHwgc2hfcGF0aFtlXVtqXSA9PSBJTkYpIHsKICAgICAgICAgICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGlmIChzaF9wYXRoW2ldW2VdICsgc2hfcGF0aFtlXVtqXSA8IHNoX3BhdGhbaV1bal0pIHsKICAgICAgICAgICAgICAgICAgICAgICAgc2hfcGF0aFtpXVtqXSA9IHNoX3BhdGhbaV1bZV0gKyBzaF9wYXRoW2VdW2pdOwogICAgICAgICAgICAgICAgICAgICAgICBuZXh0W2ldW2pdID0gbmV4dFtpXVtlXTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gZTsgKytpKSB7CiAgICAgICAgICAgICAgICBmb3IgKGludCBqID0gMTsgaiA8PSBlOyArK2opIHsKICAgICAgICAgICAgICAgICAgICBjb3V0IDw8IChzaF9wYXRoW2ldW2pdID49IElORiA/IC0xIDogc2hfcGF0aFtpXVtqXSkgPDwgIiAiOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgY291dCA8PCAnXG4nOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIHZlY3RvcjxpbnQ+IGZpbmRfcGF0aChpbnQgdSwgaW50IHYpIHsKICAgICAgICB2ZWN0b3I8aW50PiBwYXRoID0ge3V9OwogICAgICAgIGlmIChuZXh0W3VdW3ZdID09IC0xKSB7CiAgICAgICAgICAgIHJldHVybiB7fTsKICAgICAgICB9CiAgICAgICAgd2hpbGUgKHUgIT0gdikgewogICAgICAgICAgICB1ID0gbmV4dFt1XVt2XTsKICAgICAgICAgICAgcGF0aC5wdXNoX2JhY2sodSk7CiAgICAgICAgfQogICAgICAgIHJldHVybiBwYXRoOwogICAgfQp9OwoKaW50MzJfdCBtYWluKCkgewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKDApOwogICAgaW50IG4sIG07CiAgICBjaW4gPj4gbiA+PiBtOwogICAgRmxveWQgZmxveWQobik7CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBtOyArK2kpIHsKICAgICAgICBpbnQgdSwgdiwgYzsKICAgICAgICBjaW4gPj4gdSA+PiB2ID4+IGM7CiAgICAgICAgZmxveWQuYWRkX2VkZ2UodSwgdiwgYyk7CiAgICB9CiAgICBmbG95ZC5zb2x2ZSgpOwogICAgcmV0dXJuIDA7Cn0=