Călinuţa tocmai a găsit o foaie de hârtie pe care este desenat un graf orientat aciclic cu N noduri şi M arce, fiecare arc având o distanţă de valoare întreagă.

Cerință

Dându-se N, M şi cele M arce cu distanţele dintre ele, trebuie să calculaţi pentru Călinuţa distanţa minimă dintre fiecare două noduri.

Date de intrare

Fișierul de intrare graph.in conține pe prima linie numerele naturale N și M separate printr-un singur spațiu, iar pe următoarele M linii se află câte 3 numere A, B şi C, reprezentând un arc de la A către B de lungime C.

Date de ieșire

Fișierul de ieșire graph.out conține N linii cu câte N valori separate prin câte un spaţiu, reprezentând matricea drumurilor minime. Dacă nu există drum de la un nod a la un nod b, valoarea care trebuie afişată este x.

Restricții și precizări:

• N <= 1500
• M <= 30 000
• Numerele nodurilor sunt valori cuprinse între 1 şi N
• Lungimea arcelor aparţine intervalului [-1000; 1000]
• Pentru 25% din teste N <= 150 şi M <= 1000
• Pentru alte 40% din teste N <= 1000

Exemplu

graph.in

8 9
1 2 7
2 3 -1
2 4 -2
2 7 3
8 2 -2
8 6 3
5 4 2
5 6 6
6 7 -5

graph.out

0 7 6 5 x x 10 x 
x 0 -1 -2 x x 3 x 
x x 0 x x x x x 
x x x 0 x x x x 
x x x 2 0 6 1 x 
x x x x x 0 -5 x 
x x x x x x 0 x 
x -2 -3 -4 x 3 -2 0

#include <bits/stdc++.h>


using namespace std;

ifstream cin("graph.in");
ofstream cout("graph.out");

vector<vector<pair<int, int>>> G(30001);
int n, m, x, y, c, a[1501][1501];

void lee(int nod){
    int d[1501];
    for(int i = 1; i <= n; ++i)
        d[i] = 1000000001;
    queue<int> Q;
    Q.push(nod);
    d[nod] = 0;
    while(!Q.empty()){
        int x = Q.front();
        for(auto i:G[x]){
            if(d[i.first] > d[x] + i.second)
                d[i.first] = d[x] + i.second, Q.push(i.first);
        }
        Q.pop();
    }
    for(int i = 1; i <= n; ++i)
        if(d[i] != 1000000001)
            a[nod][i] = d[i];
        else
            a[nod][i] = -1000000000;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }
    for(int i = 1; i <= n; ++i){
        lee(i);
    }
    for(int i = 1; i <= n; ++i, cout << '\n')
        for(int j = 1; j <= n; ++j)
            if(a[i][j] != -1000000000)
                cout << a[i][j] << ' ';
            else cout << 'x' << ' ';
    return 0;
}