P7831 [CCO 2021] Travelling Merchant

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

无

无

#### 样例 #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