Bridges

San Bytecisco is a beautifully situated coastal town. It consists of $n$ small but densely populated islands, numbered from $1$ to $n$. Some pairs of islands are joined by bridges that carry two-way (bidirectional) traffic. At most one bridge may connect any pair of islands. The islands are connected so that every island can be reached from every other island using the bridges alone.

Byteasar and Bytie are planning a bike trip in San Bytecisco. Starting from island $1$, they want to visit every island, cross every bridge exactly once, and return to where they started, island $1$. In other words, they are looking for a closed route (an Eulerian circuit) that begins at island $1$, uses every bridge exactly once, and ends back at island $1$.

The trouble is the wind. It is very windy along the coast, and especially so on the bridges. Depending on its speed and direction, the wind makes a bridge harder to cross, and to a different degree for each of the two directions. For every bridge and every direction of crossing, assume the opposing wind speed is constant.

Define the tiresomeness of a route as the maximum opposing wind speed among all the (bridge, direction) crossings it uses. Among all routes that satisfy the requirements, make this tiresomeness as small as possible, and report that minimum value.

The first line contains two integers $n$ and $m$ separated by a single space ($2 \le n \le 1000$, $1 \le m \le 2000$), the number of islands and the number of bridges. Islands are numbered from $1$ to $n$, and bridges from $1$ to $m$.

Each of the next $m$ lines describes one bridge. Line $i+1$ contains four integers $a_i, b_i, l_i, p_i$ separated by single spaces ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le l_i, p_i \le 1000$). Bridge $i$ connects islands $a_i$ and $b_i$; the opposing wind speed is $l_i$ when crossing from $a_i$ to $b_i$, and $p_i$ when crossing from $b_i$ to $a_i$.

If no route meeting the requirements exists, print NIE (Polish for 'no') on a single line. Otherwise, print a single integer: the minimum possible tiresomeness, that is, the smallest achievable maximum opposing wind speed over all valid routes.