3856: 【CSP2022】沙漠旅行

文件读写 travel.in/out 


小X 和小Y 某天头脑发热,携手来到了一片沙漠,作为自己的假期旅行。然而,天有不测风云,突然刮起沙尘暴,两人不幸走散了。小X 为了找到小Y,决定拿出自己新研发的定位和传送系统。由于该系统还不成熟,只能找到地图上有限的n个关键点,并支持m对关键点之间的单向传送。传送理论上只需要耗费 1 的时间,但同样由于该系统还不成熟,有些传送需要耗费 2 的时间才能保证传送的安全。 尽管系统不成熟,对于小X自己以及小Y所在的位置自然是格外敏感的。因此,小X 所在的位置是关键点 1,小Y 所在的位置是关键点 n ,且小X 一定能找到小 Y。 现在,小X 想用最短的时间找到小Y,希望你能帮他算出这个时间。

输入的第一行包含两个整数n 和m。 接下来m行,每行包含三个整数ui,vi,wi (1≤i≤m，ui≠vi,),表示可以用wi的时间从ui单向传送到vi。

输出一行包含一个整数,表示小 X 找到小 Y 的最短时间。 【样例说明】 1→2→4 与 1→3→4 两种方案都只需要 3 的时间。 【数据规模和约定】 各规模均有一半数据满足所有wi=1。 对于 30%的数据,1≤n≤300。 对于 60%的数据,1≤n≤5×10^3。 对于 100%的数据,1≤n≤3×10^5,1≤m≤5×10^5。

4 5
1 3 1
2 4 2
1 2 2
3 4 2
2 4 1

3