Bessie와 자매 Elsie는 외양간에서 좋아하는 밭으로 가려 하며 정확히 동시에 출발하고 정확히 동시에 도착하려 합니다.

농장은 $N$개의 밭($1 \leq N \leq 100$)으로 이루어지고 번호는 $1 \dots N$입니다. $1$은 외양간, $N$은 좋아하는 밭입니다. 언덕 옆이라 $X < Y$이면 $X$가 $Y$보다 높습니다. $M$개의 길이 밭 쌍을 연결하지만 가팔라 내리막으로만 갈 수 있습니다. 예를 들어 $5$와 $8$의 길은 $5 \to 8$로 갈 수 있지만 반대는 오르막이라 안 됩니다. 한 쌍에는 최대 하나의 길만 있으므로 $M \leq N(N-1)/2$입니다.

같은 길의 시간이 다를 수 있습니다. 예를 들어 Bessie는 $10$ 단위, Elsie는 $20$입니다. 밭 사이 길에서만 시간이 듭니다. 서두르므로 밭을 지나는 시간은 사실상 0이며 어디에서도 기다리지 않습니다.

좋아하는 밭에 정확히 동시에 도착할 최단 시간을 구하세요.

입력

첫째 줄에는 공백으로 구분된 $N$와 $M$이 주어집니다.

다음 $M$개의 줄은 네 정수 $A$ $B$ $C$ $D$로 길을 나타냅니다. $A$와 $B$($A < B$)는 연결된 밭, $C$는 Bessie의 시간, $D$는 Elsie의 시간입니다. $C$와 $D$는 모두 $1 \ldots 100$ 범위입니다.

출력

동시에 도착할 최소 시간을 한 정수로 출력하세요. 불가능하거나 Bessie 또는 Elsie가 좋아하는 밭에 전혀 갈 수 없다면 한 줄에 IMPOSSIBLE을 출력하세요.

예제

입력 1

3 3
1 3 1 2
1 2 1 2
2 3 1 2

출력 1

2

참고

Bessie는 각 길에서 두 배 빠르지만 Bessie가 $1 \to 2 \to 3$, Elsie가 $1 \to 3$으로 가면 동시에 도착합니다.

출제: Nick Wu, 2015