Description

给定一个 $n$ 个点 $m$ 条边的无向带权图，请输出这个图的邻接矩阵的存储结构。

Format

Input

第一行输入两个整数 $n,m$，表示$n$ 个点 $m$ 条边。

接下来 $m$ 行每行输入三个数字 $u,v,w$ 代表 $u-v$ 之间的一条边，且边的长度为 $w$

Output

输出为一个 $n\times n$ 的矩阵 $dis$，其中 $dis_{i,j}$ 的含义为 $i\to j$ 的距离，若 $i$ 无法 直接 到达 $j$ 输出 $-1$ 即可。

Samples

3 2
1 2 3
1 3 4

0 3 4
3 0 -1
4 -1 0

Limitation

$1\leq n\leq 1000,1\leq u,v,w\leq 1000$