正值海灯节，居住在枫丹的芙宁娜，想要找远在璃月的好朋友胡桃一起出游。但是从枫丹前往璃月的道路有很多，不同的道路要收取不同的路费，傻傻的芙宁娜不知道怎么走才是最便宜的路线，她便带着地图来寻求你的帮助。

只见地图上标注了 n 个城邦编号 1, 2, . . . ,n 。特别的， 1 号城邦为枫丹， n 号城邦为璃月。同时地图上还标注了 m 条连接两个城邦的道路以及每条道路的过路费，道路双向均可通行，请你根据这张地图，告诉芙宁娜最便宜的路线的花费。

第一行包含两个整数 n, m ( 2 ≤ n ≤ 1000, 1 ≤ m ≤  ) ，具体含义见题面。

接下来 m 行，每行包含三个整数 u, v, w ( 1 ≤ u < v ≤ n, 1 ≤ w ≤ 1000 ) ，表示从 u 号城邦到 v 号城邦的路费为 w ，保证输入没有自环、重边。

如果没有路线可以到达，一行中输出 -1 。

否则，一行中输出一个整数，表示最便宜路线的花费。