作为一名热衷于旅行的游客，Bartek 每年都会出发去探索新的国家和大陆。为了实现这一目标，他必须仔细优化自己的旅行成本——这在携带两个行李箱旅行时尤为重要。为了节省开支，他依靠朋友来寄存行李箱，并住在由当地编程竞赛组织者支付费用的酒店里。

世界上有 $n$ 个城市（编号从 1 到 $n$）和 $m$ 条航线。每条航线由四个数字 $(a, b, c, d)$ 描述，表示从城市 $a$ 到城市 $b$ 的单程航班，费用为 $c$，行李限额为 $d$ 个行李箱。Bartek 可以多次使用同一条航线，每次携带最多 $d$ 个行李箱。机票价格与行李数量无关。行李箱不能单独乘机，但在每个城市，Bartek 都有一个朋友，可以根据需要寄存任意数量的行李箱，寄存时长和次数不限。

Bartek 有两个行李箱，想要在两个城市之间旅行。对于每一对城市 $(x, y)$，请找出如果 Bartek 从城市 $x$ 出发并携带两个行李箱，最终带着这两个行李箱到达城市 $y$ 的最小总旅行成本。如果对于给定的城市对无法到达，则输出 -1。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 400; 0 \le m \le 500\,000$)，分别表示城市数量和航线数量。

接下来的 $m$ 行，每行包含四个整数 $a_i, b_i, c_i, d_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i; 1 \le c_i \le 10^9; 0 \le d_i \le 2$)，描述一条航线。两个城市之间可能存在多条航线。某些城市可能没有出发或到达的航线。

输出格式

输出 $n$ 行，每行包含 $n$ 个由空格分隔的整数。在第 $i$ 行中，第 $j$ 个整数应为从城市 $i$ 到城市 $j$ 携带两个行李箱旅行的最小总成本，如果无法到达，则输出 -1。

样例

输入 1

5 7
1 2 500 2
2 3 100 1
3 5 20 2
5 4 5 1
4 2 1 0
3 4 40 2
5 4 77 1

输出 1

0 500 726 751 746
-1 0 226 251 246
-1 -1 0 40 20
-1 -1 -1 0 -1
-1 -1 -1 131 0

说明

例如，从城市 1 到城市 3，Bartek 可以按以下方式旅行：

$1 \to 2$（放下 1 个行李箱）$\to 3$（放下 1 个行李箱）$\to 5 \to 4 \to 2$（取回 1 个行李箱）$\to 3$（取回 1 个行李箱）

总成本为 $500 + 100 + 20 + 5 + 1 + 100 = 726$。