题目描述

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

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

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

输出样例

2

提示

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