1951. 相遇时间

【题目描述】

贝茜和她的姐姐要从谷仓到她们喜欢的地方旅行，他们同时离开谷仓，并同时到达她们喜欢的地点。

农场是一个集合，包括N个地域（1≤N≤100）编号1 ..N，1号地点包含了谷仓，N号是她们喜欢的地域。

农场建在山边，X＜Y表示X的海拔比Y高。有M条路径连接各个地域。然而，由于每条路径是相当陡峭的，所以只能下坡。例如，一条路径连接地域5和地域8，可在5 --> 8方向行进,而不能是其他方向，因为这将是上坡的。每两个地域由至多一条路径连接，所以M <= N（N-1）/2。

贝茜和爱丽丝可能以不同的时间通过一条路径；例如，贝茜可能需要10单位的时间，爱丽丝需要20或更多。此外，贝茜和爱丽丝只在旅行时的路径上消耗时间，因为她们很忙，他们总是零时间通过一个地域，不会在任何地方等待。

请帮助确定最短时间，贝茜和爱丽丝必须采取以完全相同的时刻达到他们最喜欢的地域。

【输入格式】

输入的第一行包含N和M，用一个空格隔开。

之后的每一行描述一个路径使用四个整数A，B，C，D，其中A和B（A< B）是路径，C是贝茜通过路径所需的时间，D是爱丽丝通过路径所需的时间。C和D在范围1..100。

【输出格式】

一个整数，给出所需的最小时间，贝茜和爱丽丝到达她们最喜欢的地域，在同一时刻到达。

如果这是不可能的，或者是没有办法到达贝茜和爱丽丝喜欢的地域，输出单独一行， "IMPOSSIBLE"。

【样例输入】

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

【样例输出】

2

【提示】

样例解释：

贝茜在每条路径上速度都是爱丽丝的两倍，贝茜走路径1--> 2 --> 3，爱丽丝走路径1 --> 3，她们会同一时间到达。

【来源】

在此键入。