{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e贝西搬到了一个小农场,有时喜欢回去拜访她最好的朋友之一。她不想太快回到她以前的家,因为她喜欢沿途的风景。她决定走次短路径,而不是最短路径。她知道一定有一条次短路径。\u003c/p\u003e\u003cp\u003e乡村由 \u003ci\u003eR\u003c/i\u003e (1 ≤ \u003ci\u003eR\u003c/i\u003e ≤ 100,000) 条双向道路组成,每条道路连接两个交叉口中的一个,方便地编号为 1..\u003ci\u003eN\u003c/i\u003e。贝西从交叉口 1 开始,她的朋友(目的地)在交叉口 \u003ci\u003eN\u003c/i\u003e。\u003c/p\u003e\u003cp\u003e次短路径可以与任何最短路径共享道路,并且可以折返,即多次使用相同的道路或交叉口。次短路径是长度比最短路径长的最短路径(即,如果存在两条或更多条最短路径,则次短路径是长度比这些路径长但不比任何其他路径长的路径)。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第1行:两个用空格分隔的整数:\u003ci\u003eN\u003c/i\u003e 和 \u003ci\u003eR\u003c/i\u003e\r\u003cbr\u003e第2行..\u003ci\u003eR\u003c/i\u003e+1:每行包含三个用空格分隔的整数:\u003ci\u003eA\u003c/i\u003e, \u003ci\u003eB\u003c/i\u003e, 和 \u003ci\u003eD\u003c/i\u003e,描述连接交叉口 \u003ci\u003eA\u003c/i\u003e 和 \u003ci\u003eB\u003c/i\u003e 的道路,长度为 \u003ci\u003eD\u003c/i\u003e (1 ≤ \u003ci\u003eD\u003c/i\u003e ≤ 5000)"}},{"title":"输出","value":{"format":"HTML","content":"第1行:节点 1 到节点 \u003ci\u003eN\u003c/i\u003e 之间的次短路径的长度"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 4\r\n1 2 100\r\n2 4 200\r\n2 3 250\r\n3 4 100\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e450\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"两条路线:1 -\u0026gt; 2 -\u0026gt; 4 (长度100+200\u003d300) 和 1 -\u0026gt; 2 -\u0026gt; 3 -\u0026gt; 4 (长度100+250+100\u003d450)"}}]}