146. graph

#include <bits/stdc++.h>

using namespace std;

ifstream fin("graph.in");
ofstream fout("graph.out");

const int INF = 2e9L;
const int NMAX = 1500;
int N, M, dp[NMAX + 1][NMAX + 1], deg[NMAX + 1];
vector<pair<int,int>> G[NMAX + 1];
vector<int> top_order;

void init() {
    for(int i = 0; i <= N; ++i)
        for(int j = 0; j <= N; ++j)
            dp[i][j] = INF;
}

void read() {
    fin >> N >> M;
    while(M--) {
        int u, v, w;
        fin >> u >> v >> w;
        G[u].emplace_back(v, w);
        ++deg[v];
    }
}

void topological_sort() {
    queue<int> Q;
    for(int u = 1; u <= N; ++u)
        if(deg[u] == 0)
            Q.emplace(u);
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        top_order.emplace_back(u);
        for(const pair<int,int> &v : G[u]) {
            --deg[v.first];
            if(deg[v.first] == 0)
                Q.emplace(v.first);
        }
    }
}

void solve() {
    for(int source = 1; source <= N; ++source) {
        dp[source][source] = 0;
        for(const int &u : top_order) {
            if(dp[source][u] == INF)
                continue;
            for(const pair<int,int> &v : G[u])
                if(dp[source][v.first] > dp[source][u] + v.second)
                    dp[source][v.first] = dp[source][u] + v.second;
        }
    }
}

void print() {
    for(int i = 1; i <= N; ++i, fout << '\n')
        for(int j = 1; j <= N; ++j, fout << ' ')
            if(dp[i][j] == INF)
                fout << 'x';
            else
                fout << dp[i][j];
}

int main() {
    read();
    init();
    topological_sort();
    solve();
    print();
}