graph

#include<cstdio>
#include<vector>
#include<queue>
#define infile "graph.in"
#define outfile "graph.out"
#define nMax 1513
#define inf (1<<29)

using namespace std;

vector < pair<int, int> > v[nMax];
int dp[nMax];
int n, m;

void read() {
    scanf("%d %d\n", &n, &m);

    for (int i = 0; i < m; ++i) {
        int x, y, z;
        scanf("%d %d %d\n", &x, &y, &z);
        v[x].push_back(make_pair(y, z));
    }
}

void bf(int x) {

    queue <int> q;

    for (int i = 0; i < n+1; ++i) {
        dp[i] = inf;
    }

    dp[x] = 0; q.push(x);

    while(q.size()) {
        int x = q.front();

        for (unsigned j = 0; j < v[x].size(); ++j) {
            if (dp[v[x][j].first] > dp[x] + v[x][j].second) {
                dp[v[x][j].first] = dp[x] + v[x][j].second;
                q.push(v[x][j].first);
            }
        }

        q.pop();
    }
}

void solve() {

    for (int i = 0; i < n; ++i) {
        bf(i+1);

        for (int j = 0; j < n; ++j) {
            if (dp[j+1] == inf) {
                printf("x ");
            } else {
                printf("%d ", dp[j+1]);
            }
        }

        printf("\n");
    }
}

int main() {
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    read();
    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}