#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

const int maxn = 1e3 + ;

int mp[maxn][maxn];

int n, m;

int main() {

    scanf("%d%d", &n, &m);

    for (int i = ; i <= n; i++) {

        for (int j = ; j < m; j++) {

            if (i == j) mp[i][j] = ;

            else mp[i][j] = INF;

        }

    }

    int u, v, w;

    for (int i = ; i <= m; i++) {

        scanf("%d%d%d", &u, &v, &w);

        mp[u][v] = w;

    }

    for (int k = ; k <= n; k++) {

        for (int i = ; i <= n; i++) {

            for (int j = ; j <= n; j++) {

                mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);

            }

        }

    }

    for (int i = ; i <= n; i++) {

        for (int j = ; j <= n; j++) {

            printf("%10d", mp[i][j]);

        }

        printf("\n");

    }

    return ;

}

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

const int INF = 0x3f3f3f3f;

const int maxn = 1e3 + ;

struct Node {

    int v, c;   //c为到v点的最短路长度

    Node(int _v = ,int _c=): v(_v),c(_c) {}

    friend bool operator < (Node a, Node b) {

        return a.c > b.c;

    }

};

struct Edge {

    int v, cost;

    Edge(int _v = , int _cost = ) : v(_v), cost(_cost) {}

};

vector<Edge> E[maxn];

void add_edge(int u, int v, int w) {

    E[u].push_back(Edge(v, w));

}

int n, m;

bool vis[maxn];

bool dis[maxn];

void Dijkstra(int n, int start) {

    memset(vis, , sizeof vis);

    for (int i = ; i <= n; i++) dis[i] = INF;

    priority_queue<Node> q;

    while (!q.empty()) q.pop();

    dis[start] = ;

    q.push(Node(start, ));

    Node tmp;

    while (!q.empty()) {

        tmp = q.top();   q.pop();

        int u = tmp.v;

        if (vis[u]) continue;

        vis[u] = true;

        for (int i = ; i < E[u].size(); i++) {

            int v = E[tmp.v][i].v;

            int cost = E[u][i].cost;

            if (!vis[v] && dis[v] > dis[u] + cost) {

                dis[v] = dis[u] + cost;

                q.push(Node(v, dis[v]));

            }

        }

    }

}

int main() {

    scanf("%d%d", &n, &m);

    int u, v, w;

    for (int i = ; i < m; i++) {

        scanf("%d%d%d", &u, &v, &w);

        add_edge(u, v, w);

    }

    Dijkstra(n, );

    for (int i = ; i <= n; i++) printf("%d ", dis[i]);

    return ;

}

relax(u, v) {

    dist[v] = min(dist[v], dist[u] + edge_len(u, v));

}

for (i = ; i <= n; i++) {

    dist[i] = edge_len(S, i);

}

for (i = ; i < n; i++) {

    for each edge(u, v) {

        relax(u, v);

    }

}

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

const int INF = 0x3f3f3f3f;

const int maxn = 1e3 + ;

struct Edge {

    int v, cost;

    Edge(int _v,int _cost): v(_v),cost(_cost) {}

};

vector<Edge> E[maxn];

void add_edge(int u, int v, int w) {

    E[u].push_back(Edge(v, w));

}

bool vis[maxn];

int cnt[maxn];

int dis[maxn];

bool spfa(int n, int start) {

    memset(vis, , sizeof vis);

    for (int i = ; i <= n; i++)  dis[i] = INF;

    vis[start] = true;

    dis[start] = ;

    queue<int> q;

    while (!q.empty()) q.pop();

    q.push(start);

    memset(cnt, , sizeof cnt);

    cnt[start] = ;

    while (!q.empty()) {

        int u = q.front();

        q.pop();

        vis[u] = true;

        for (int i = ; i < E[u].size(); i++) {

            int v = E[u][i].v;

            if (dis[v] > dis[u] + E[u][i].cost) {

                dis[v] = dis[u] + E[u][i].cost;

                if (!vis[v]) {

                    vis[v] = true;

                    q.push(v);

                    if (++cnt[v]> n) return false;

                }

            }

        }

    }

    return true;

}