Meeting Time

Bessie and her sister Elsie want to travel from the barn to their favorite field. They want to leave the barn at exactly the same moment and reach the field at exactly the same moment.

The farm has $N$ fields ($1 \le N \le 16$) numbered $1$ through $N$. Field $1$ holds the barn and field $N$ is the favorite field. The farm sits on the side of a hill, so field $X$ is higher than field $Y$ whenever $X < Y$. There are $M$ paths, each joining a pair of fields. Every path is steep enough that a cow can follow it only downhill. A path joining field $5$ and field $8$ can be followed from $5$ to $8$ but not the other way, because that direction is uphill. At most one path joins any pair of fields, so $M \le N(N-1)/2$.

Bessie and Elsie need different amounts of time on the same path. One path might cost Bessie $10$ units of time and Elsie $20$. The cows spend time only while walking a path. They are in a hurry, so they cross a field in zero time and never wait anywhere.

Find the smallest total time in which Bessie and Elsie can reach their favorite field at the same moment.

The first line contains $N$ and $M$, separated by a space.

Each of the next $M$ lines describes one path with four integers $A$, $B$, $C$, $D$. Fields $A$ and $B$ are the fields the path joins, with $A < B$. The value $C$ is the time Bessie needs on that path and $D$ is the time Elsie needs. Both $C$ and $D$ are between $1$ and $1000$.

Print, on a single line, the minimum time in which both cows reach the favorite field at the same moment. If no such time exists, or if the cows cannot reach field $N$ at all, print IMPOSSIBLE on a single line. When $N = 1$ the barn is already the favorite field, so print $0$.

In the first example Bessie is twice as fast as Elsie on every path. Even so, if Bessie walks 1 -> 2 -> 3 and Elsie walks 1 -> 3, they arrive at the same moment.