21826번 - Travelling Merchant 다국어

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

The first line contains the two integers N and M (2 ≤ N, M ≤ 200 000).

The i-th of the next M lines contains the four integers a_i, b_i, r_i, and p_i (1 ≤ a_i, b_i ≤ N, a_i ≠ b_i, 0 ≤ r_i, p_i ≤ 10⁹). Note that there may be any number of routes between a pair of cities.

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.

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