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

Input

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

Output

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