Pondo Shortest Paths

You are given a connected undirected graph with $n$ vertices and $m$ weighted edges. For every pair of vertices, determine the shortest-path distance between them.

Input

The first line contains two space-separated integers $n$ and $m$.

Each of the next $m$ lines contains three integers $u$, $v$, and $w$, denoting an undirected edge between $u$ and $v$ with weight $w$. There may be multiple edges between the same pair of vertices, and there may be self-loops.

Vertices are numbered $1$ through $n$.

Output

Print $n$ lines. The $i^{th}$ line should contain $n$ space-separated integers $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$, where $a_{u,v}$ is the shortest-path distance from $u$ to $v$.

Constraints

• $1 \le n \le 100$
• $1 \le m \le \frac{n \cdot (n - 1)}{2}$
• $1 \le u, v \le n$
• $1 \le w \le 100$

Example 1

4 5
1 2 5
1 3 9
2 3 1
4 2 3
3 4 2

0 5 6 8
5 0 1 3
6 1 0 2
8 3 2 0