Canadian Computing Olympiad: 2021 Day 2, Problem 1

A merchant would like to make a business of travelling between cities, moving goods from one city to another in exchange for a profit. There are $N$ cities and $M$ trading routes between them.

The $i$-th trading route lets the merchant travel from city $a_i$ to city $b_i$ (in only that direction). In order to take this route, the merchant must already have at least $r_i$ units of money. After taking this route, the total amount of money the merchant has will increase by $p_i$ units, with a guarantee that $p_i\ge 0$.

For each of the $N$ cities, we would like to know the minimum amount of money required for a merchant to start in that city and be able to keep travelling forever.

Input Specification

The first line contains the two integers $N$ and $M$ $(2\le N,M\le 200000)$. The $i$-th of the next $M$ lines contains the four integers $a_i$, $b_i$, $r_i$, and $p_i$ $(1\le a_i,b_i\le N,a_i\ne b_i,0\le r_i,p_i\le {10}^9)$. Note that there may be any number of routes between a pair of cities.

For 4 of the 25 available marks, $N,M\le 2000$.

For an additional 5 of the 25 available marks, $p_i=0$ for all $i$.

Output Specification

On a single line, output $N$ space-separated integers, where the $i$-th is the answer if the merchant were to start at city $i$. This answer is either the minimum amount of money, or -1 if no amount of money can be sufficient.

Sample Input

5 5
3 1 4 0
2 1 3 0
1 3 1 1
3 2 3 1
4 2 0 2

Sample Output

2 3 3 1 -1

Explanation for Sample Output

Starting from city 2 with 3 units of money, the merchant can cycle between cities 2, 1, and 3.