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