다리

산바이트시스코(San Bytecisco)는 해안에 자리 잡은 아름다운 마을이다. 이 마을은 $1$번부터 $n$번까지 번호가 붙은, 작지만 인구가 밀집한 섬 $n$개로 이루어져 있다. 일부 섬 쌍은 다리로 연결되어 있으며, 이 다리로는 양방향 통행이 가능하다. 두 섬 사이에는 다리가 최대 한 개만 놓일 수 있다. 모든 섬은 다리만 이용해서 서로 오갈 수 있도록 연결되어 있다.

바이트아사르(Byteasar)와 바이티(Bytie)는 산바이트시스코로 자전거 여행을 떠나려 한다. 두 사람은 $1$번 섬에서 출발하여 모든 섬을 방문하고, 모든 다리를 정확히 한 번씩 건넌 뒤 출발한 곳인 $1$번 섬으로 돌아오려고 한다. 즉, $1$번 섬에서 시작해 모든 다리를 한 번씩만 지나 다시 $1$번 섬으로 돌아오는 닫힌 경로(오일러 회로)를 찾는 것이다.

문제는 바람이다. 해안은 바람이 세고, 특히 섬과 섬을 잇는 다리 위에서는 더욱 그렇다. 바람의 세기와 방향에 따라, 같은 다리라도 건너는 방향에 따라 맞바람의 세기가 다르다. 각 다리를 각 방향으로 건널 때 받는 맞바람의 세기는 일정하다고 가정한다.

경로의 힘든 정도는, 그 경로에서 건넌 모든 (다리, 방향) 조합의 맞바람 세기 중 최댓값으로 정한다. 조건을 만족하는 경로 중에서 이 힘든 정도가 가장 작아지도록 할 때, 그 최솟값을 구하라.

첫째 줄에 두 정수 $n$과 $m$이 공백 하나로 구분되어 주어진다 ($2 \le n \le 1000$, $1 \le m \le 2000$). 각각 섬의 수와 다리의 수를 나타낸다. 섬은 $1$번부터 $n$번까지, 다리는 $1$번부터 $m$번까지 번호가 붙어 있다.

이어지는 $m$개의 줄에 다리의 정보가 주어진다. $i+1$번째 줄에는 네 정수 $a_i, b_i, l_i, p_i$가 공백 하나로 구분되어 주어진다 ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le l_i, p_i \le 1000$). 이는 $i$번 다리가 $a_i$번 섬과 $b_i$번 섬을 연결하며, $a_i$에서 $b_i$로 건널 때 맞바람 세기가 $l_i$, $b_i$에서 $a_i$로 건널 때 맞바람 세기가 $p_i$임을 뜻한다.

조건을 만족하는 경로가 존재하지 않으면 첫째 줄에 NIE(폴란드어로 '아니오')를 출력한다. 존재하면, 가능한 경로들의 힘든 정도(즉 건넌 모든 방향별 맞바람 세기의 최댓값) 중 최솟값을 정수 하나로 출력한다.