{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eベッシーは小さな農場に引っ越し、時々最も親しい友人の一人を訪れるのを楽しんでいます。彼女は古い家にあまり早く着きたくないので、途中の風景を楽しむことが好きです。彼女は最短経路ではなく、2番目に短い経路を取ることに決めました。彼女は必ずしも2番目に短い経路があると知っています。\u003c/p\u003e\u003cp\u003e田舎は\u003ci\u003eR\u003c/i\u003e (1 ≤ \u003ci\u003eR\u003c/i\u003e ≤ 100,000) 本の双方向道路で構成されており、それぞれがN (1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 5000) 個の交差点を結んでいます。交差点は便宜上1..\u003ci\u003eN\u003c/i\u003eまで番号が付けられています。ベッシーは交差点1から出発し、彼女の友人(目的地)は交差点\u003ci\u003eN\u003c/i\u003eにいます。\u003c/p\u003e\u003cp\u003e2番目に短い経路は、最短経路と同じ道を共有することがあり、バックトラックすることがあります。つまり、同じ道や交差点を複数回使用することがあります。2番目に短い経路は、最短経路よりも長い距離である最短経路です(つまり、2つ以上の最短経路が存在する場合、2番目に短い経路はそれらよりも長く、他のどの経路よりも短い距離である経路です)。\u003c/p\u003e"}},{"title":"入力","value":{"format":"HTML","content":"Line 1: 2つのスペースで区切られた整数: \u003ci\u003eN\u003c/i\u003e と \u003ci\u003eR\u003c/i\u003e\r\u003cbr\u003eLines 2..\u003ci\u003eR\u003c/i\u003e+1: 各行には、交差点 \u003ci\u003eA\u003c/i\u003e と \u003ci\u003eB\u003c/i\u003e を結ぶ長さ \u003ci\u003eD\u003c/i\u003e の道を表す3つのスペースで区切られた整数が含まれています(1 ≤ \u003ci\u003eD\u003c/i\u003e ≤ 5000)"}},{"title":"出力","value":{"format":"HTML","content":"Line 1: 交差点1から交差点 \u003ci\u003eN\u003c/i\u003e までの2番目に短い経路の長さ"}},{"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":"2つの経路: 1 -\u0026gt; 2 -\u0026gt; 4 (長さ100+200\u003d300) と 1 -\u0026gt; 2 -\u0026gt; 3 -\u0026gt; 4 (長さ100+250+100\u003d450)"}}]}