ROY-FLOYD

#include <bits/stdc++.h>

using namespace std;

ifstream f ("roy-floyd.in");
ofstream g ("roy-floyd.out");

int n, m, a[128][128], x, y, C;

void Read () {
    f >> n >> m;
    while (m --) {
        f >> x >> y >> C;
        a[x][y] = C;
    }
}

void RF () {
    for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
    if ((a[i][j] > a[i][k] + a[k][j] || a[i][j] == 0) && a[i][k] && a[k][j] && i != j)
    a[i][j] = a[i][k] + a[k][j];
}

void Solve () {
    RF ();
    for (int i = 1; i <= n; ++i, g << '\n')
    for (int j = 1; j <= n; ++j)
    if (i != j && a[i][j] == 0) g << "-1 ";
    else g << a[i][j] << ' ';
}

void Close () {
    f.close();
    g.close();
}

int main() {
    Read ();
    Solve ();
    Close ();
    return 0;
}