Cho đồ thị có hướng có trọng số gồm n đỉnh và m cung.

Tìm độ dài đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị.

Lưu ý: trọng số có thể âm.

INPUT

Dòng đầu là 2 số nguyên dương: n, m (n ≤ 420; m ≤ $10^6$)

m dòng tiếp theo, mỗi dòng gồm 3 số nguyên u, v, c cho biết có cung u-v với trọng số c. (1 ≤ u, v ≤ n; |c| ≤ $10^6$).

OUTPUT

Ghi ra n dòng, mỗi dòng gồm n số: số thứ j trên dòng i là độ dài đường đi ngắn nhất từ đỉnh i đến đỉnh j. Nếu không có đường đi thì ghi ra chữ X.

VÍ DỤ

Input

5 7
1 3 8
1 5 -7
4 1 12
2 5 8
2 4 5
3 5 1
5 4 -4

Output

0 X 8 -11 -7 
16 0 24 4 8 
9 X 0 -3 1 
12 X 20 0 5 
8 X 16 -4 0