3717: 旅行

旅行是一件非常令人愉快的事情，但即使是人生经验丰富的旅行家们也不得不经常面临一个现实问题——玩耍五分钟，坐车一小时。 为了有效地解决这个问题， Efve 决定将旅行可能用到的交通线路全部用电脑记下来，他希望能找出一条旅行线路，使自己尽可能愉悦地享受旅程。 但是， Efve 并不认为花费时间最少的线路就一定最能使自己愉悦。比起在 people mountain people sea 的地铁上站半小时还得换站三次，他宁愿选择坐在相对空旷的公交上睡五十分钟直接到达目的地。 因此， Efve 为交通线路定义了一个愉悦值，接着结合各种数据，算出了每条交通线路的愉悦值，其中不乏一些完美线路，不会对 Efve 的心情产生任何影响。 然而，由于 Efve 的心情飘忽不定，他每次旅行前也会给自己算出一个初始愉悦值。而且在到达目的地之前， Efve 每经过一条愉悦值低于自身当前愉悦值的线路，他的愉悦值就会降低到与该线路愉悦值相同。 现在给出 Efve 记录的所有交通线路（包括起点、终点、愉悦值和花费时间），以及某次旅行的出发点、目的地和旅行前 Efve 的初始愉悦值。 Efve 希望你能告诉他：

①到达目的地时，他的愉悦值最大是多少？

②在保证愉悦值最大的前提下，路上花费的总时间最少是多少？

第一行，两个整数 N 和 M，表示 Efve 记录的 M 条线路中，共有 N 个不同的地点，标号为 1 到 N。

以下 M 行，每行四个整数 xi、 yi、 hi 和 ti，表示在地点 xi 和 yi 之间有一条愉悦值为 hi，花费时间为 ti 的双向交通线路。特殊的，当 hi 的值为 -1 时，表示该线路是一条完美线路。

最后一行，三个整数 S、 T 和 H，表示 Efve 打算从地点 S 出发前往地点 T，而他的初始愉悦值为 H。

如果 Efve 完成不了他的旅行计划，输出一行： Impossible! 否则，输出两行：

第一行，一个整数，表示 Efve 到达地点 T 时的最大愉悦值。

第二行，一个整数，表示 Efve 在保证到达地点 T 时愉悦值最大的前提下，花费的最少总时间。  

5 6
1 2 7 5
1 3 4 2
2 4 -1 10
2 5 2 4
3 4 10 1
4 5 8 5
1 5 10

7
20