[USACO15JAN] Meeting Time S

#### 题目描述： $\texttt{Bessie}$ 和她的妹妹 $\texttt{Elsie}$ 想从粮仓去她们最喜欢的田地，也就是能够使她们一起从粮仓离开，并且能同一时间到达的田地。 这个农场是由 $N$ 块 $(1\leq N\leq 100)$ 编号为 $1\cdots N$ 的田地构成的，第一块田地就是粮仓，并且第 $N$ 块田地是她们最喜欢的田地。 这个农场建在山的一边，所以，如果 $X < Y$ 的话则满足第 $X$ 块田地的高度要高于第 $Y$ 块田地的高度。在这之中，有 $M$ 条交错纵横的路径将不同的田地连接起来。 不过，显而易见的是，因为每条路都太陡了，所以这些小路只能沿着从高到低的方向走。例如，一条连接第 $5$ 块田地和 $8$ 块田地的小路只能沿着 $5\to 8$ 的方向走，而不能沿着其他方向，因为那样会成为上坡路。每两块田地最多只能有一条路径相连接，所以一定有 $M \leq \dfrac{N(N-1)}{2}$。 有可能的是，$\texttt{Bessie}$ 和 $\texttt{Elsie}$ 两个人走同一条小路会耗费不同的时间；比如，通过同一条小路，$\texttt{Bessie}$ 可能会耗费 $10$ 个单位的时间，而 $\texttt{Elsie}$ 会耗费 $20$ 个单位的时间。 此外，$\texttt{Bessie}$ 和 $\texttt{Elsie}$ 只会在通过连接两块田地的小路时耗费时间——因为她们太匆忙了，在穿过田地时不会耗费任何时间，也从来不在任何地方停下来等待。 现在，请你判断出，能够满足使 $\texttt{Bessie}$ 和 $\texttt{Elsie}$ 同时出发并且同时到达她们喜欢的田地的最短的时间。 #### 输入格式： 第一行输入 $N$ 和 $M$，中间用空格分开。 接下来的 $M$ 行，每行有四个整数 $A,B,C,D$，其中，$A$ 和$B(A<B)$ 代表着两块用这条小路连接的田地，$C$ 代表 $\texttt{Bessie}$ 通过这条小路的时间，而 $D$ 代表 $\texttt{Elsie}$ 通过这条小路的时间。$C$ 和 $D$ 均在 $1\cdots100$ 的范围之内。 #### 输出格式： 一个整数，输出的是能够使两人同时出发并且同时到达目的地的最短时间，如果没有满足条件的答案，则输出 `IMPOSSIBLE`。 #### 说明与提示： $\texttt{Bessie}$ 在每一条路都比 $\texttt{Elsie}$ 快两倍。 如果 $\texttt{Bessie}$ 经过 $1\to 2\to 3$ 的路线，$\texttt{Elsie}$ 经过 $1\to 3$ 的路线，他们可以同时到达。

Bessie and her sister Elsie want to travel from the barn to their favorite field, such that they leave at exactly the same time from the barn, and also arrive at exactly the same time at their favorite field. The farm is a collection of N fields (1 <= N <= 100) numbered 1..N, where field 1 contains the barn and field N is the favorite field. The farm is built on the side of a hill, with field X being higher in elevation than field Y if X < Y. An assortment of M paths connect pairs of fields. However, since each path is rather steep, it can only be followed in a downhill direction. For example, a path connecting field 5 with field 8 could be followed in the 5 -> 8 direction but not the other way, since this would be uphill. Each pair of fields is connected by at most one path, so M <= N(N-1)/2. It might take Bessie and Elsie different amounts of time to follow a path; for example, Bessie might take 10 units of time, and Elsie 20. Moreover, Bessie and Elsie only consume time when traveling on paths between fields -- since they are in a hurry, they always travel through a field in essentially zero time, never waiting around anywhere. Please help determine the shortest amount of time Bessie and Elsie must take in order to reach their favorite field at exactly the same moment.

INPUT: (file meeting.in) The first input line contains N and M, separated by a space. Each of the following M lines describes a path using four integers A B C D, where A and B (with A < B) are the fields connected by the path, C is the time required for Bessie to follow the path, and D is the time required for Elsie to follow the path. Both C and D are in the range 1..100.

OUTPUT (file meeting.out) A single integer, giving the minimum time required for Bessie and Elsie to travel to their favorite field and arrive at the same moment. If this is impossible, or if there is no way for Bessie or Elsie to reach the favorite field at all, output the word IMPOSSIBLE on a single line.

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

2 

SOLUTION NOTES: Bessie is twice as fast as Elsie on each path, but if Bessie takes the path 1->2->3 and Elsie takes the path 1->3 they will arrive at the same time.