Infinite Traveling Salesman

A country has n cities and m directed roads. A traveling salesman wants to travel forever. The i-th road goes from city a_i to city b_i. However, he can only take a road if his current asset is at least r_i dollars. After traveling this road, his asset increases by p_i dollars. Note that in this problem, p_i is nonnegative so the asset never decreases.

To travel indefinitely, he must eventually enter a cycle. In other words, given an initial asset X, if we consider the graph containing only the roads with r_i ≤ X, then from every city there must exist a path to some cycle (a strongly connected component with more than one vertex or containing a self-loop). Your task is to determine the minimum initial asset X required such that, starting from any city, the salesman can travel indefinitely.

Note: All roads guarantee that the asset will not decrease because p_i ≥ 0. Thus, if an edge is available with a given initial asset X, it will remain available in subsequent steps.

The problem can be solved by binary searching on X from 0 to max(r_i). For each candidate X, filter the graph by keeping only the roads with r_i ≤ X, then perform a Strongly Connected Components (SCC) decomposition. Mark all vertices lying in SCCs of size > 1 or with a self-loop as "cycle vertices." Then, by reversing the graph and doing a breadth-first search starting at all cycle vertices, check if every vertex can reach a cycle. The smallest X meeting this condition is the answer.

inputFormat

The first line contains two integers n and m — the number of cities and roads respectively.

Each of the following m lines contains four integers: a, b, r, and p, which describe a directed road from city a to city b that can be taken if the current asset is at least r. After taking this road, the asset increases by p.

It is guaranteed that all p values are nonnegative.

outputFormat

Output a single integer — the minimum initial asset required such that, starting from any city, the traveling salesman can travel indefinitely.

sample

3 3
1 2 10 5
2 3 10 0
3 2 10 0

10