고속도로 현대화

바이트나라의 왕이 최근 일부 고속도로를 현대화하라는 칙령을 내렸다. 왕국의 기술자들은 각 고속도로를 현대화하는 비용을 이미 계산해 두었고, 모든 고속도로의 길이도 알려져 있다. 각 고속도로는 양방향이며 두 도시를 잇는다. 이제 남은 문제는 어떤 고속도로를 현대화할지 고르는 것이다. 수석 기술자가 이 질문을 왕에게 가져가자, 왕은 잠시 생각한 뒤 다음 두 가지 조건을 제시했다.

• 현대화된 고속도로만 이용해서 수도에서 곧 국제 박람회가 열릴 도시까지 갈 수 있어야 한다.
• 현대화하는 고속도로 1킬로미터당 평균 비용이 가능한 한 작아야 한다.

이 조건을 만족하도록 현대화할 고속도로의 집합을 고르되, 고른 고속도로들의 1킬로미터당 평균 현대화 비용이 최소가 되도록 하고, 그 비용을 표준 출력으로 출력하는 프로그램을 작성하라. 수도에서 박람회 도시로 갈 수만 있으면, 그 경로 위에 직접 놓이지 않은 고속도로도 자유롭게 현대화 대상에 포함할 수 있으며, 그렇게 포함한 고속도로의 비용과 길이도 평균에 함께 반영된다.

첫째 줄에 공백 하나로 구분된 두 정수, 도시의 수 $n$ 과 고속도로의 수 $m$ 이 주어진다 ($2 \le n \le 100$, $1 \le m \le 500$). 도시는 $1$ 번부터 $n$ 번까지 번호가 매겨져 있다. 수도는 $1$ 번 도시이고, 박람회는 $2$ 번 도시에서 열린다. 이어지는 $m$ 개의 줄에는 각각 하나의 고속도로가 공백으로 구분된 네 정수 $a$, $b$, $c$, $d$ 로 주어진다 ($1 \le a, b \le n$, $a \ne b$, $1 \le c, d \le 100$). 이는 도시 $a$ 와 $b$ 를 잇고, 현대화 비용이 $c$ 바이트달러이며 길이가 $d$ 인 고속도로를 나타낸다.

왕의 조건을 만족시킬 수 없다면 한 줄에 NIE 라는 한 단어만 출력한다. 그렇지 않으면 최적해에서의 1킬로미터당 최소 평균 현대화 비용을 출력한다. 즉, 고른 고속도로들의 현대화 비용의 합을 그 길이의 합으로 나눈 값이다. 결과는 기약분수 형태, 곧 나눗셈 기호 / 로 구분된 두 정수로 출력한다 (정수는 $x/1$ 꼴로 출력한다).