3750. T4 Meeting Time 集合时间
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 贝茜和艾希想从牛棚到它们最喜欢的田地去，它们希望可以同时从牛棚出发，并且恰好同时到达最喜欢的田地。 农场中共有 $ N $ 块田地，编号 $ 1∼N $ 。 牛棚在 $ 1 $ 号田地，它们最喜欢的田地是 $ N $ 号田地。 农场建在山坡上，如果 $ X<Y $ ，则编号为 $ X $ 的田地的海拔高度比编号为 $ Y $ 的田地高。 共有 $ M $ 条道路，每条道路连接两个田地。 由于每条道路都比较陡峭，所以道路只能沿着下坡方向行进。 例如，如果田地 $ 5 $ 和田地 $ 8 $ 之间存在一条道路，则该道路只能沿 $ 5\to8 $ 的方向行进。 每对田地之间最多存在一条道路相连。 贝茜和艾希走完同一条路所花费的时间可能不同。 例如，贝茜可能需要花费 $ 10 $ 个单位时间，而艾希可能需要花费 $ 20 $ 个单位时间。 此外，贝茜和艾希只会在沿途道路上花费时间，它们不会在中途做任何停留，穿过田地的时间也忽略不计。 请帮助它们确定为了恰好同一时间到达它们最喜欢的田地所必须花费的最短时间。 ## 输入格式 第一行包含 $ N $ 和 $ M $ 。 接下来 $ M $ 行，每行包含四个整数 $ A,B,C,D $ 表示田地 $ A $ 和 $ B $ 之间存在一条道路，贝茜走过该道路所需时间为 $ C $ ，艾希走过该道路所需时间为 $ D $ 。 ## 输出格式 输出它们为了恰好同一时间到达它们最喜欢的田地所必须花费的最短时间。 如果做不到，则输出 `IMPOSSIBLE`。 ## 输入 ```in1 3 3 1 3 1 2 1 2 1 2 2 3 1 2 ``` ## 输出 ```out1 2 ``` ## 提示 ## 数据范围 $ 1\leN\le16 $ , $ 1\leM\le\frac{N(N-1)}{2} $ , $ 1\leA<B\leN $ , $ 1\leC,D\le1000 $