만나는 시각

베시와 동생 엘시는 헛간에서 가장 좋아하는 목초지까지 가려고 한다. 두 소는 헛간을 똑같은 시각에 떠나서 목초지에도 똑같은 시각에 닿고 싶다.

농장은 $1$번부터 $N$번까지 번호가 붙은 목초지 $N$개($1 \le N \le 16$)로 이루어진다. $1$번 목초지에 헛간이 있고 $N$번 목초지가 가장 좋아하는 목초지다. 농장이 언덕 사면에 있어서 $X < Y$이면 $X$번 목초지가 $Y$번 목초지보다 높다. 목초지 두 곳을 잇는 길이 $M$개 있다. 길이 워낙 급해서 내려가는 방향으로만 지날 수 있다. 예를 들어 $5$번과 $8$번을 잇는 길은 $5$번에서 $8$번으로만 갈 수 있고, 반대 방향은 오르막이라 갈 수 없다. 목초지 한 쌍을 잇는 길은 많아도 하나이므로 $M \le N(N-1)/2$이다.

같은 길이라도 베시와 엘시가 지나는 데 걸리는 시간은 다르다. 베시는 $10$, 엘시는 $20$이 걸리는 길이 있을 수 있다. 두 소는 길을 지날 때만 시간을 쓴다. 서두르는 중이라 목초지는 시간을 전혀 쓰지 않고 지나가고, 어디에서도 기다리지 않는다.

두 소가 가장 좋아하는 목초지에 똑같은 시각에 닿으려면 시간이 얼마나 걸리는지, 그 최솟값을 구하라.

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다.

다음 $M$개 줄에는 길 하나를 나타내는 네 정수 $A$, $B$, $C$, $D$가 주어진다. $A$와 $B$는 그 길이 잇는 두 목초지의 번호이고 $A < B$이다. $C$는 베시가 그 길을 지나는 데 걸리는 시간, $D$는 엘시가 걸리는 시간이며 둘 다 $1$ 이상 $1000$ 이하다.

두 소가 가장 좋아하는 목초지에 똑같은 시각에 닿을 수 있는 최소 시간을 한 줄에 출력한다. 그런 시간이 없거나 두 소가 $N$번 목초지에 아예 갈 수 없으면 한 줄에 IMPOSSIBLE을 출력한다. $N = 1$이면 헛간이 곧 가장 좋아하는 목초지이므로 $0$을 출력한다.

첫 번째 예제에서 베시는 어느 길에서나 엘시보다 두 배 빠르다. 그래도 베시가 1 -> 2 -> 3으로, 엘시가 1 -> 3으로 가면 도착 시각이 같아진다.