[CCO2021] Travelling Merchant

一个国家有 $n$ 个城市和 $m$ 条单向道路，一个旅行商在这些城市之间旅行。 第 $i$ 条道路从城市 $a_i$ 到城市 $b_i$，只有当他的资产不少于 $r_i$ 元才可以走这条道路，走过这条道路之后他的资产会增加 $p_i$ 元。 他希望自己可以永远不停的游走下去，于是他想知道从任意一个城市出发至少需要多少元初始资产。

第一行，两个整数 $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

#### 样例 #1 解释 以第 $2$ 座城市为例：从第 $2$ 座城市出发，初始资产 $3$ 元，则可以在第 $2, 1, 3$ 三座城市无限绕圈。 #### 数据范围 对于 $\frac{2}{7}$ 的数据，$2 \leq n, m \leq 2 \times 10^3$； 对于另 $\frac{15}{49}$ 的数据，$p_i = 0$； 对于 $100\%$ 的数据，$2 \leq n, m \leq 2 \times 10^5$，$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$0 \leq r_i, p_i \leq 10^9$，**保证没有自环但可能有重边**。 #### 题目来源 [CCO2021](https://cemc.math.uwaterloo.ca/contests/computing/2021/index.html) D2T1