#백준_11404 플로이드 - Java

# 유형 : 플로이드-와샬 알고리즘

# 플로이드 와샬 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제

***시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다는 점만 유의할것

package bj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p11404 {
	static int INF = 1000000000;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int arr[][] = new int[n+1][n+1];
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(i==j)
					continue;
				else
					arr[i][j] = INF;
			}
		}
		
		int m = Integer.parseInt(br.readLine());
		StringTokenizer st;
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int val = Integer.parseInt(st.nextToken());
			arr[u][v] = Math.min(arr[u][v], val);
		}
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				for(int k=1; k<=n; k++) {
					arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
				}
			}
		}
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(arr[i][j]>=INF)
					System.out.print("0 ");
				else
					System.out.print(arr[i][j]+ " ");
			}System.out.println();
		}
	}
}