Description

给定一个 $n$ 个点 $m$ 条边的有向图，可能有重边。请你输出一个二维矩阵 $dis$，其中 $dis_{i,j}$ 的含义为 $i\to j$ 的最短路。边权的范围是 $0\leq w\leq 10^3$

Format

Input

第一行输入两个整数 $n,m$ 其中 $1\leq n\leq 100,1\leq m\leq 10^4$。

Output

输出一个 $n\times n$ 的二维矩阵。

Samples

3 3
1 2 5
2 3 3
1 3 10

0 5 8 
-1 0 3 
-1 -1 0