Contest1263/F.cpp

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 101;
int a[MAXN][MAXN];
int n, m;
void Floyd(){
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(a[i][j] > a[i][k] + a[k][j]){
                    a[i][j] = a[i][k] + a[k][j];
                }
            }
        }
    }
}

int main(){
    while(cin >> n >> m){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i != j)
                    a[i][j] = 9999999;
                else a[i][j] = 0;
            }
        }
        for(int i = 1; i <= m; i++){
            int x, y, z;
            cin >> x >> y >> z;
            if(a[x][y] > z)
            a[x][y] = a[y][x] = z;
        }
        Floyd();
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(j!=1){
                    cout << " ";
                }
                cout << a[i][j];
            }
            cout << endl;
        }
    }
}