该国恰好有 n 个城市,编号为 1 到 n 的正整数。每个城市都有一个机场。
此外,只有一家航空公司运营 m 个航班。不幸的是,要使用它们,您需要成为该公司的常客,也就是说,只有您之前已经乘坐过至少 di 航班,您才有机会享受从 ai 城市到 bi 城市的航班 i。
请注意,航班 i 正好从 ai 城市飞往 bi 城市。它不能用于从bi市飞往ai市的航班。一个有趣的事实是,可能会有一些具有美丽天空景色的休闲航班,其起点和终点都在同一个城市。
您需要从城市 1 前往城市 n。不幸的是,您以前从未乘坐过飞机。为了到达 n 城市,您至少需要乘坐多少趟航班?
请注意,同一航班可以多次使用。
输入
第一行包含两个整数 n 和 m (2 ≤ n ≤ 150, 1 ≤ m ≤ 150) — 该国的城市数量和公司提供的航班数量。
接下来的 m 行包含数字 ai, bi, di (1 ≤ ai, bi ≤ n, 0 ≤ di ≤ 109),代表从城市 ai 到城市 bi 的航班号 i,仅对至少乘坐过 di 航班的客户开放。
输出
如果无法通过航空公司从城市 1 到达城市 n,请打印“不可能”(不带引号)。
但如果至少有一种方法,请打印一个整数 - 到达目的地点所需的最少航班数。
示例
输入 #1
3 2 1 2 0 2 3 1
输出 #1
2
输入 #2
2 1 1 2 100500
输出 #2
Impossible
输入 #3
3 3 2 1 0 2 3 6 1 2 0
输出 #3
8