题目描述

给定一张 $n$ 个点 $m$ 条边的有向图。一开始你在 $1$ 号节点，你要走到 $n$ 号节点去。只有当你已经走过了至少 $d_i$ 条边时，你才能走第 $i$ 条边。

问最少要走多少条边，或判断无法到达。

输入格式

第一行两个整数 $n,m$，$n,m \le 150$。

接下来 $m$ 行每行三个整数 $a_i, b_i, d_i$，表示一条有向边 $<a_i, b_i>$，边权为 $d_i$，$d_i \le 10^9$。

输出格式

输出一个整数表示答案，若无解则输出 Impossible。

3 2
1 2 0
2 3 1

2

2 1
1 2 100500

Impossible

3 3
2 1 0
2 3 6
1 2 0

8