Johnny 非常喜欢徒步旅行。不幸的是，他的膝盖大不如前，下坡对他来说尤其困难。因此，他下周六的计划如下：他将从“三湖谷”（Valley of Three Lakes）出发，攀登“末日山”（Mount Doom）。然后，他将乘巴士前往“五湖谷”（Valley of Five Lakes）并攀登“迷雾山”（Misty Mountain）。由于膝盖的问题，至关重要的是，行程的两个部分（不计巴士行程）都必须仅由上坡路段组成。Johnny 已经准备好了一份所有上坡路段的列表，并确定了每个路段的长度。每个路段连接两个地点。由于他很容易感到厌倦，他行程的两个部分也必须是严格不相交的。请帮助 Johnny 确定整个行程，使得总步行距离尽可能短。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，用空格分隔，分别表示地点的数量和路段的数量（$2 \le n \le 1\,000$，$1 \le m \le 10\,000$）。接下来的 $m$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $x_i$，用空格分隔，描述了第 $i$ 个可能的路段：从地点 $a_i$ 到地点 $b_i$，长度为 $x_i$（$1 \le a_i, b_i \le n$，$1 \le x_i \le 10^6$）；每个这样的路段都是上坡，即其终点位置的海拔高度严格大于其起点位置的海拔高度。

下一行包含整数 $s_1, t_1$，最后一行包含 $s_2, t_2$（$1 \le s_i, t_i \le n$），用空格分隔，分别表示行程两部分的起点和终点，即“三湖谷”到“末日山”，以及“五湖谷”到“迷雾山”。你可以假设 $s_1 \neq t_1$ 且 $s_2 \neq t_2$，但除此之外不应做任何其他假设。

输出格式

输出应仅包含一行，即最小可能的总步行距离，如果无法按照 Johnny 的要求规划行程，则输出单词 NIE。

样例

样例输入 1

5 5
1 3 1
2 3 1
3 4 1
3 5 1
1 4 3
1 4
2 5

样例输出 1

5

说明 1

上述示例描述了以下地点和路段。从 1 到 4 以及从 2 到 5 存在唯一一种选择不相交路径的方式，如图中加粗部分所示。对应的总步行距离为 5。

样例输入 2

4 5
1 2 1
1 3 1
1 4 1
2 4 1
3 4 1
1 4
2 3

样例输出 2

NIE

说明 2

上述示例描述了以下地点和路段。无法从 2 出发并到达 3。