题目描述

一个商人想要在城市间旅行来经商，他会将货物从一个城市运往另一个城市来谋利。现有 $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\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$。