题目描述
在EVE游戏中,宇宙被划分成为许多区域,每个区域中都有数目不定的星门,可以通过星门来跳跃到特定的区域(星门是双向的)。
现在你正参与BBE联军与MLGBD联盟的会战,但由于飞船受损,需要尽快回到后方的友军空间站进行维护。
试编写程序,计算出所须的最短的返回空间站时间。
为了简化问题,我们约定飞船所在的位置为区域1,空间站所在的位置为区域N。
问题规模:
对于80%的数据,1<N<=10000,1<M<50000;
对于100%的数据,1<N<=30000,1<M<150000,1<=X[],Y[]<=N,1<=Z[]<=4096;
输入格式
第1行,两个整数N,M,分别为区域的总数和星门的总数;
第2..M+1行,每行三个整数X[i],Y[i],Z[i],分别为星门连接的两个区域,以及跳跃所需时间;
输出格式
一个整数,返回空间站所需的最短时间。
样例输入
样例输出