Description

Bessie和她的妹妹Elsie想要从谷仓旅行到他们最喜欢的地区去。她们会在同一时间离开谷仓，也希望要在同一时

间到达她们的目的地地区。农场由N个地区组成，分别编号为1..N (1 <= N <= 100)，谷仓位于1号区域，而她们的

目的地是N号区域。由于农场是依山而建的，两个区域之间会有高度差，编号小的地区海拔高于编号大的地区的海

拔，即1号地区海拔最高，N号地区海拔最低。会有M条小路两两连接不同地区。因为山路过于陡峭，路只允许以下

坡的方式行走。比如就一条路连接了5号区域和8号区域，那么只允许从5号区域前往8号区域而不允许反向行走。每

两个地区之间至多只有一条路，所以M <= N(N-1)/2。Bessie和Elsie走路所花费的时间是不一样的。比如，走同一

条路，Bessie会需要10个单位时间，而Elsie会要20个。请注意，因为她们在赶时间，所以只会在路上花费时间，

进入或者离开一个区域不需要花费时间，而且她们也不会停下来等对方。请帮忙计算出Bessie和Elsie最短需要多

少时间才能同时出发且同时到达她们的目的地。

Format

Input

第一行包含两个以空格分隔的整数，分别为N和M。

接下来M行描述连接区域之间的路的情况

每一行给出四个以空格分隔的整数A B C D，表示A区域和B区域之间有一条路，

Bessie需要C个单位时间来走完这条路，而Elsie需要D个单位时间来走。

C和D都在区间1..100内。

Output

输出一个整数。即Bessie和Elsie同时出发且同时达到N号区域所需要的最少时间。

如果无法到达N号区域或者不可能同时到达，请输出单词 "IMPOSSIBLE"（引号不用输出）。

Samples

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.

Limitation