有一个拥有 $N$ 个城市和 $M$ 条双向道路的国家。在第 $i$ 条道路上行驶需要花费 $T_i$ 分钟，并花费 $C_i$ 库纳（克罗地亚货币）。

为了让到达度假目的地的旅程尽可能愉快，你希望让它尽可能快且尽可能便宜。具体来说，你当前位于 $1$ 号城市，并且希望最小化从 $1$ 号城市到达某个城市所花费的总金额与总时间（即你行驶过的所有道路的总和）的乘积。对于除 $1$ 号城市以外的每个城市，输出所需的最小乘积；如果 $1$ 号城市与该城市不连通，则输出 -1。

输入格式

输入的第一行包含两个整数 $N$ ($1 \le N \le 2000$)，表示城市的数量，以及 $M$ ($1 \le M \le 2000$)，表示道路的数量。

接下来的 $M$ 行，每行包含四个整数 $A_i, B_i, T_i, C_i$ ($1 \le A_i, B_i \le N$，$1 \le T_i, C_i \le 2000$)，表示有一条连接城市 $A_i$ 和 $B_i$ 的道路，行驶该道路需要 $T_i$ 分钟，且花费 $C_i$ 库纳。

两个城市之间可能存在多条道路，但不会存在连接城市自身的道路。

输出格式

你必须输出 $N - 1$ 行。

在第 $i$ 行中，输出到达城市 $i + 1$ 所需的最小乘积，如果 $1$ 号城市与城市 $i + 1$ 不连通，则输出 -1。

数据范围

对于占总分 $40\%$ 的测试数据，满足 $1 \le N, M, T_i, C_i \le 100$。

样例

输入样例 1

4 4
1 2 2 4
3 4 4 1
4 2 1 1
1 3 3 1

输出样例 1

8
3
14

输入样例 2

4 5
1 2 1 7
3 1 3 2
2 4 5 2
2 3 1 1
2 4 7 1

输出样例 2

7
6
44

输入样例 3

3 2
1 2 2 5
2 1 3 3

输出样例 3

9
-1

说明

第二个样例的解释：

• 为了到达城市 2，你需要行驶道路 1，花费 1 分钟和 7 库纳，因此所需的乘积为 7。
• 为了到达城市 3，你需要行驶道路 2，花费 3 分钟和 2 库纳，因此所需的乘积为 6。
• 为了到达城市 4，你需要依次行驶道路 2、4、5，总共花费 11 分钟和 4 库纳，因此所需的乘积为 44。