P2865 [USACO06NOV] Roadblocks G

Bessie 搬到了一个小农场，有时喜欢回去拜访她的一个好朋友。她不想太快到达她的旧家，因为她喜欢沿途的风景。她决定选择第二短的路径而不是最短的路径。她知道一定存在某条第二短路径。 乡村由 $R(1\le R\le100,000)$ 条双向道路组成，每条道路连接 $N(1\le N\le5000)$ 个交叉路口中的两个，这些交叉路口被方便地编号为 $1$ 到 $N$。Bessie 从交叉路口 $1$ 出发，她的朋友（目的地）在交叉路口 $N$。 第二短路径可以与任何最短路径共享道路，并且可以回溯，即多次使用相同的道路或交叉路口。第二短路径是长度比最短路径长的最短路径（即，如果存在两条或多条最短路径，第二短路径是长度比这些路径长但不比任何其他路径长的路径）。

无

无

两条路径：$1\to2\to4$（长度 $100+200=300$）和 $1\to2\to3\to4$（长度 $100+250+100=450$）。 （由 ChatGPT 4o 翻译）