5753 - 相遇问题

贝丽斯和她的姐姐艾丽斯想从谷仓走到她们最喜爱的牧场。她们在同一时间离开谷仓，也在同一时间到达最喜爱的牧场。

整个农场是一个有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~1000。

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

【数据范围】

对于20%的数据满足：N≤5。

对于60%的数据满足：M≤90。

对于100%的数据满足：1≤N≤16，M≤N（N-1）/2。

课课通