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 200\,000)~. 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 2\,000~.

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.