P7831 [CCO 2021] Travelling Merchant

A country has $n$ cities and $m$ directed roads, and a travelling merchant travels among these cities. The $i$-th road goes from city $a_i$ to city $b_i$. He can use this road only when his assets are at least $r_i$ yuan. After taking this road, his assets increase by $p_i$ yuan. He wants to be able to keep travelling forever without stopping, so he wants to know, starting from each city, the minimum initial assets required.

The first line contains two integers $n, m$. The next $m$ lines each contain four integers $a_i, b_i, r_i, p_i$ on the $i$-th line.

Output one line with $n$ integers. If the answer for the $i$-th city does not exist, then the $i$-th integer is $-1$. Otherwise, it is the minimum initial assets required (in yuan).

#### Sample #1 Explanation Take city $2$ as an example: starting from city $2$ with initial assets of $3$ yuan, he can loop forever among cities $2, 1, 3$. #### Constraints For $\frac{2}{7}$ of the testdata, $2 \leq n, m \leq 2 \times 10^3$. For another $\frac{15}{49}$ of the testdata, $p_i = 0$. For $100\%$ of the testdata, $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$, **it is guaranteed that there are no self-loops but there may be multiple edges**. #### Source [CCO2021](https://cemc.math.uwaterloo.ca/contests/computing/2021/index.html) D2T1 Translated by ChatGPT 5