# Appreciation

/*
 * Problem :: 11404 / 플로이드
 *
 * Kind :: Floyd-Warshall
 *
 * Insight
 * - 문제이름이 플로이드다
 *   + 플로이드-워셜 or 플로이드-와샬 알고리즘을 사용해주자
 *     # 원리 by 위키피디아
 *       1 에서 N 까지 번호가 매겨진 V 를 꼭짓점으로 갖는 그래프 G 를 생각하자
 *       그 후 i 에서 j 로 집합 {1, 2, ..., k} 의 꼭짓점들 만을 경유지로 거쳐 가는
 *       최단 경로를 반환하는 함수 shortestPath(i,j,k) 를 생각하자
 *       -> shortestPath(i,j,k) 는 다음 중 한 가지에 속한다
 *          k 를 통과하지 않는 경로 / k 를 통과하는 경로
 *          => shortestPath(i,j,k)
 *             = min(shortestPath(i,j,k-1),
 *                   shortestPath(i,k,k-1) + shortestPath(k,j,k-1))
 *
 * Point
 * - 예제 입력을 유심히 살펴보면
 *   a, b, c 로
 *   1 4 1
 *   ...
 *   1 4 2
 *   의 입력이 들어온다
 *   + min 을 써서 항상 dp[a][b] 가 최소가 되도록 유지하자!
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
#define INF (100*100000+1)

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    int dp[N+1][N+1];
    fill(&dp[1][1], &dp[N][N+1], INF);
    for (int i=1; i<=N; i++) { dp[i][i] = 0; }
    int M; cin >> M;
    for (int i=0; i<M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dp[a][b] = min(dp[a][b], c);
    }

    // Process
    for (int m=1; m<=N; m++) {
        for (int f=1; f<=N; f++) {
            for (int t=1; t<=N; t++) {
                if (dp[f][t] > dp[f][m] + dp[m][t]) {
                    dp[f][t] = dp[f][m] + dp[m][t];
                }
            }
        }
    }

    // Control : Output
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++) {
            cout << ((dp[i][j] == INF) ? 0 : dp[i][j]) << ' ';
        } cout << endl;
    }
}

// Helper Functions
/* None */