常旅客航线

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

有 $n$ 座城市和 $m$ 条单向航线。第 $i$ 条航线从 $a_i$ 飞往 $b_i$，但只有在此前已经乘坐过至少 $d_i$ 次航班时才可以乘坐。航线可以重复乘坐，也可以是起终点相同的观光航线。

你从城市 $1$ 出发，此前没有乘机记录。求到达城市 $n$ 最少需要乘坐的航班数。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $a_i,b_i,d_i$，描述一条航线。

输出格式

若可以到达城市 $n$，输出最少航班数；否则输出 Impossible。

样例输入 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

数据范围

对所有数据：$2\le n\le150$，$1\le m\le150$，$1\le a_i,b_i\le n$，$0\le d_i\le10^9$。

各子任务数据彼此独立计分。