← 返回题目列表

Codeforces · 576/D

D. 常客航班

中文机器翻译题面 查看原题

该国恰好有 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