Problem Description

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.

Input Format

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 Format

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).

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

Hint

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 D2T1

Translated by ChatGPT 5