## CCO '21 P4 - Travelling Merchant

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 1G

Author:
Problem type

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 cities and trading routes between them.

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

For each of the 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 and . The -th of the next lines contains the four integers , , , and . Note that there may be any number of routes between a pair of cities.

For 4 of the 25 available marks, .

For an additional 5 of the 25 available marks, for all .

#### Output Specification

On a single line, output space-separated integers, where the -th is the answer if the merchant were to start at city . 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.