题目描述

贝丽斯和她的姐姐艾丽斯想从谷仓走到他们最喜爱的牧场。她们在同一时间离开谷仓，也在同一时间到达最喜爱的牧场。
整个农场是一个有 \(N\) 个牧场,\(1\) 号牧场就是谷仓,\(N\) 号牧场是她们最喜爱的牧场。整个农场是建在一个山坡上的,如果 \(X<Y\),则代表 \(X\) 号牧场比 \(Y\) 牧场要高。有 \(M\) 条路径连接一堆牧场然而,由于每条路径都很陡,每条路只能向下的方向走。比如，一条连接 \(5\) 号和 \(8\) 号农场的路只能从 \(5\) 走到 \(8\) 而不能反过来,因为那样就是向山上走了。每对牧场之间最多有一条路径,故 \(M≤N(N-1)/2\)。

贝丽斯和艾丽斯可能需要不同的时间来走过一条路径。例如,贝丽斯可能花 \(10\) 个单位的时间,而艾丽斯会花 \(20\) 个单位,而且她们只在路径上花时间,在牧场上是不花时间的。

请帮助决定贝丽斯和艾丽斯至少要花多少时间，使她们能同时到达她们最喜爱的农场。

格式

输入格式

第 \(1\) 行是 \(N\) 和 \(M\),用一个空格分开。
接下来的 \(M\) 行,每行有 \(4\) 个整数 \(A、B、C、D\)。表示 \(A\) 牧场和 \(B\) 牧场是被连接的，\(C\) 是贝丽斯经过这条路要花的时间，\(D\) 是艾丽斯经过这条路要花的时间。\(C\) 和 \(D\) 的范围是 \(1 \sim 1000\)。

输出格式

一行一个整数,表示贝丽斯和艾丽斯至少要花多少时间使她们能同时到达她们最喜爱的农场。如果这是不可能的,或者根本就没有路径使她们能到达她们最喜爱的农场,在一行输出“\(\texttt{IMPOSSIBLE}\)”。

样例1

样例输入1

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

样例输出1

2

样例解释

贝丽斯在每条路径上都比艾丽斯走得速度快 \(1\) 倍;但是如果贝丽斯采用路径 \(1→2→3\)，艾丽斯采用路径 \(1→3\),那么她们将在同一时间到达。

限制

对于 \(20\%\) 的数据满足:\(N≤5\)。
对于 \(60\%\) 的数据满足:\(M≤90\)。
对于 \(100\%\) 的数据满足:\(1≤N≤16，M≤N(N-1)/2\)。