题目描述

贝西和她的妹妹埃尔西想从谷仓到他们的 最喜欢的领域，使他们离开在同一时间从 谷仓，也正好在同一时间到达他们最喜欢的地方 领域

农场是编号为$\red{1}$的$\red{N}$个字段$\red{（1<=N<=16）}$的集合。。$\red{N}$ 其中字段$\red{1}$包含谷仓，字段$\red{N}$是最喜欢的字段。 该农场建在一座小山的一侧，$\red{X}$地块海拔更高 如果$\red{X<Y，}$则高程比字段$\red{Y}$高。一系列$\red{M}$路径连接 字段对。然而，由于每条道路都相当陡峭，因此它可以 只能沿着下坡方向行驶。例如，路径 在$\red{5->8}$中可以遵循字段$\red{5}$与字段$\red{8}$的连接 方向，但不是相反，因为这将是上坡路。每个 场对最多由一条路径连接，因此$\red{M<=N（}$$\red{N-1）}$$\red{/2}$。

$\red{Bessie}$和$\red{Elsie}$可能需要不同的时间来跟踪 路径例如，贝西可能需要$\red{10}$个时间单位，埃尔西可能需要$\red{20}$个时间单位。 此外，贝西和埃尔西只在小路上旅行时消耗时间 在田野之间$\red{--}$因为他们很匆忙，所以他们总是旅行 在一个基本为零的时间里通过一个领域，从不等待 在任何地方

请帮助确定贝西和埃尔西的最短时间 必须采取，以达到他们最喜欢的领域在完全相同的 片刻

输入格式

第一个输入行包含$\red{N}$和$\red{M，}$由空格分隔。

以下$\red{M}$行中的每一行都使用四个整数$\red{a B}$描述了一条路径 $\red{C D，}$其中$\red{A}$和$\red{B（}$$\red{A<B）}$是由路径连接的场， $\red{C}$是贝西沿着路径所需的时间，$\red{D}$是 $\red{Elsie}$走这条路所需的时间。$\red{C}$和$\red{D}$都在 范围$\red{1...}$$\red{1000}$

输出格式

单个整数，给出贝西和 埃尔西将前往他们最喜欢的领域，并在同一时刻抵达。 如果这是不可能的，或者如果贝西或埃尔西无法到达 最喜欢的字段是在一行中输出单词"不可能"。

样例

输入样例

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

输出样例

2

提示

贝西在每一条路上的速度都是埃尔西的两倍，但如果贝西选择 路径$\red{1->2->3，}$$\red{Elsie}$选择路径$\red{1->3，}$他们将到达 同一时间。