U90068 城市游戏

小$A$和小$B$正在进行一个游戏。这个游戏开展于一个城市中。城市中总共包含$n$个路口，从1到$n$进行编号。某些路口之间连接着具有一定长度的双向道路，道路总共有$m$条。 小$A$正在这个城市的1号路口，想要移动到$n$号路口。小$B$的目标是尽可能阻止小$A$。他的阻止方法是：在小$A$位于某个路口上时，永久地封闭城市中的一条道路。 如果小$B$使用封闭道路的权力只有一次，你需要求出：在此基础上，如果小$A$和小$B$都使用最佳策略（即小$A$希望他走到$n$号路口的总距离尽量小，小$B$希望小$A$的移动总距离尽量大），小$A$走到$n$号路口所需要移动的总距离是多少？

第一行，两个整数$n,m$。 接下来$m$行，每行三个整数$u,v,l$，描述了一条道路连接的两个路口的编号以及道路的长度。

输出一行一个整数，为所求的答案。若小A不能到$n$达号点，输出`−1`。

对于$20\%$的数据，满足$n ≤ 200,m ≤ 1000$ 对于$40\%$的数据，满足$n ≤ 1000,m ≤ 2000$ 对于$70\%$的数据，满足$n ≤ 3000,m ≤ 10000$ 对于$100\%$的数据，满足$1 ≤ n ≤ 100000,1 ≤ m ≤ 200000$，道路长度为不超过$10^9$的正整数。