题目描述

一个商人想要在城市间旅行来经商，他会将货物从一个城市运往另一个城市来谋利。现有 $N$ 个城市和 $M$ 条贸易路线。

对于第 $i$ 条贸易路线，商人可以从城市 $a_i$ 到城市 $b_i$（只能沿这一个方向）。为了走这条路线，商人必须目前已经拥有至少 $r_i$ 单位的钱。在走过这条路线后，商人拥有的钱的总额会增长 $p_i$ 个单位，这里保证 $p_i \ge 0$。

对于这 $N$ 个城市的每一个，我们想知道如果一个商人从这个城市开始旅行，他最初至少需要有多少钱，才能使得他永远能够一直旅行下去。

输入格式

第一行两个整数 $N$ 和 $M$。

接下来 $M$ 行，第 $i$ 行有四个整数 $a_i, b_i, r_i, p_i$。注意，可能在一对城市之间有任意多条路线。

输出格式

输出一行 $N$ 个整数，用一个空格隔开，第 $i$ 个整数表示商人从城市 $i$ 开始旅行的答案。答案或者是最少钱数，或者是 $-1$，表示没有任何数量的钱是满足要求的。

样例

输入

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

输出

2 3 3 1 -1

解释
从城市 $2$ 出发，最初拥有 $3$ 个单位的钱，商人就可以在城市 $2, 1, 3$ 之间循环旅行。

数据范围与提示

对于全部数据：

• $2 \le N, M \le 2 \times 10^5$
• $1 \le a_i, b_i \le N$，$a_i \neq b_i$
• $0 \le r_i, p_i \le 10^9$

对于 $16\%$ 的分数，$N, M \le 2000$。

对于另外 $20\%$ 的分数，对于所有 $i$，都有 $p_i = 0$。