一位商人想要在城市之间进行贸易，通过将货物从一个城市运送到另一个城市来获利。共有 $N$ 个城市和 $M$ 条贸易路线。

第 $i$ 条贸易路线允许商人从城市 $a_i$ 前往城市 $b_i$（仅限该方向）。为了使用这条路线，商人必须已经拥有至少 $r_i$ 单位的钱。在走完这条路线后，商人拥有的钱的总数将增加 $p_i$ 单位，且保证 $p_i \ge 0$。

对于每一个城市，我们想知道商人从该城市出发并能够永远持续旅行下去所需的最少钱数。

输入格式

第一行包含两个整数 $N$ 和 $M$ ($2 \le N, M \le 200\,000$)。

接下来的 $M$ 行中，第 $i$ 行包含四个整数 $a_i, b_i, r_i$ 和 $p_i$ ($1 \le a_i, b_i \le N, a_i \neq b_i, 0 \le r_i, p_i \le 10^9$)。注意，一对城市之间可能存在任意数量的路线。

对于 25 分中的 4 分，满足 $N, M \le 2\,000$。

对于 25 分中的另外 5 分，满足对所有 $i$ 都有 $p_i = 0$。

输出格式

在一行中输出 $N$ 个以空格分隔的整数，其中第 $i$ 个整数表示如果商人从城市 $i$ 出发所需的答案。该答案要么是所需的最少钱数，如果无论多少钱都不足以满足条件，则输出 $-1$。

样例

输入 1

5 5
3 1 4 0
2 1 3 0
1 3 1 1
3 2 3 1
4 2 0 2

输出 1

2 3 3 1 -1

说明 1

从城市 2 出发并携带 3 单位钱，商人可以在城市 2、1 和 3 之间循环往复。