문제

승우와 찬종이는 한밭수목원의 입구($1$번 지점)에서 출발하여 가장 좋아하는 전망대($N$번 지점)까지 여행하려 한다. 두 사람은 입구에서 정확히 같은 시간에 출발하여, 전망대에도 정확히 같은 시간에 도착해야 한다.

수목원에는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 지점이 있다. ($1 \le N \le 16$) 입구는 $1$번 지점이고 전망대는 $N$번 지점이다. 수목원은 경사지에 조성되어 있어, $X < Y$일 때만 $X$번 지점에서 $Y$번 지점으로 이동할 수 있는 $M$개의 길이 있다. 즉, 모든 길은 번호가 낮은 지점에서 높은 지점으로 향하는 일방통행이다. 두 지점 사이에는 최대 하나의 길만 존재하므로, $M \le N(N-1)/2$를 만족한다.

승우와 찬종이가 같은 길을 이동하더라도 걸리는 시간은 다를 수 있다. 예를 들어, 어떤 길을 통과하는 데 승우는 $10$만큼의 시간이 걸리고 찬종이는 $20$만큼의 시간이 걸릴 수 있다. 두 사람은 서두르고 있기 때문에 지점에 머무는 시간은 없으며, 오직 길을 이동하는 데에만 시간을 소비한다.

승우와 찬종이가 정확히 같은 시각에 전망대에 도착하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지점의 수 $N$과 길의 수 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 16$; $0 \le M \le N(N-1)/2$)

다음 $M$개의 줄에는 각 길의 정보를 나타내는 네 정수 $A, B, C, D$가 공백으로 구분되어 주어진다. 이는 $A$번 지점에서 $B$번 지점으로 연결된 길을 의미하며, 승우가 이동할 때 $C$만큼, 찬종이가 이동할 때 $D$만큼의 시간이 걸린다. ($1 \le A < B \le N$; $1 \le C, D \le 1\,000$)

출력

승우와 찬종이가 전망대에 동시에 도착할 수 있는 최소 시간을 출력한다. 만약 두 사람이 동시에 도착할 수 있는 방법이 없거나, 어느 한 사람이라도 전망대에 도달할 수 있는 경로가 없다면 IMPOSSIBLE을 출력한다.

예제 입력 1

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

예제 출력 1

2