题目描述

一座地震频发的山上有$N$个村庄，编号分别为$1$至$N$。某些村庄之间有山路相连，每条山路都有一个防震等级。假如一条路的防震等级是$k（k>0）$，就表示如果发生$k$级或者小于$k$级的地震，这条山路是安然无恙的，如果发生大于$k$级的地震，这条路就会被破坏，不能通过了。
现在邮递员小明要从村庄$1$出发去村庄$N$，他想知道最高发生几级地震的情况下，他仍然能顺利到达目的地。

输入

输入数据的第一行是用空格隔开的两个整数$N$和$M$，分别表示村庄数和山路数（$2 <= N <= 50, 1 <= M <= 200$）。接下来有$M$行，每行包括三个整数$u，v，w$，表示村庄$u$和村庄$v$之间有一条防震等级为$w$的路（$1 <= u, v <= N, 1 <= w <= 20$）。路是双向的，在没有被破坏的情况下，既可以从$u$到达$v$，也可以从$v$到达$u$。两个村庄之间最多有一条路。输入数据保证在没有发生地震的时候可以从村庄$1$到达村庄$N$。
输出
输出只有一行，包含一个整数，表示最高发生几级地震的情况下仍然能到达村庄$N$。

样例输入

4 5
1 2 3
1 3 5
2 4 10
3 4 6
1 4 1

样例输出

5

提示

【说明】 在发生$5$级地震的情况下，小明可以通过$1->3->4$这条路到达村庄$4$，但如果发生$6$级地震就不能到达了。