Problem1931--逃离死亡之山

1931: 逃离死亡之山

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

「这次的目标是登上山顶,一不小心就会死哟。」
「抱着必死的决心开始特训吧!」
死亡之山上有 n个安全点,安全点之间会有道路,只有通过这些道路才能前往山顶,但每条路上都会有一个强大的对手,武力值要达到d才能战胜对手,相应的,如果打败了对手,也会得到馈赠,增加1点武力值。 
为了让27能尽早回家吃妈妈煮的饭,请你告诉他,至少要战胜多少对手,才能从山脚(1)到达山顶(n)。 

Input

第一行 n,m(n <=150,m<=150)表示安全点数和道路数目。 
接下来 m 行,每行三个数 u,v,d 表示从安全点u到安全点 v有一条道路(道路是有方向的),需要d点武力值才能安全通过。 

Output

输出一个数表示答案,如果无解,输出"impossible"。

Sample Input Copy

3 2
1 2 0
2 3 1

Sample Output Copy

2