[11404번] 플로이드

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        int a = sc.nextInt();
        int n = sc.nextInt();
        int INF = 99999999;
        int[][] ar = new int[a][a];
        int[][] dp = new int[a][a];
        
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < a; j++) {
                if (i == j) ar[i][i] = 0;
                else ar[i][j] = INF;
            }
        }
        for(int i=0;i<n;i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            int tmp = sc.nextInt();
            if(ar[x-1][y-1] !=0 && ar[x-1][y-1] > tmp)
                ar[x-1][y-1] = tmp;
        }
 
         
        for(int k=0;k<a;k++){
            for(int i=0;i<a;i++){
                for(int j=0;j<a;j++){
                    if(ar[i][k]+ar[k][j]<ar[i][j]){
                        ar[i][j] = ar[i][k]+ar[k][j];
                    }
                }
            }
        }
        for(int i=0;i<a;i++){
            for(int j=0;j<a;j++){
                if(ar[i][j]==INF){
                    ar[i][j] = 0;
                }
                if(j!=a-1)
                    System.out.print(ar[i][j]+" ");
                else
                    System.out.println(ar[i][j]);
            }
        } 
    }
  
}
 
class FastScanner {
    BufferedReader br;
    StringTokenizer st;
 
    public FastScanner(String s) {
        try {
            br = new BufferedReader(new FileReader(s));
        } catch (FileNotFoundException e) {
            throw new RuntimeException(e);
        }
    }
 
    public FastScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }
 
    String nextToken() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return st.nextToken();
    }
 
    int nextInt() {
        return Integer.parseInt(nextToken());
    }
 
    long nextLong() {
        return Long.parseLong(nextToken());
    }
 
    double nextDouble() {
        return Double.parseDouble(nextToken());
    }
 
    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}