{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Robin has moved to a small village and likes visiting one of his best friends. He usually takes a longer route, because he likes the scenery along the way. He has decided to take the second-best rather than the shortest path. He knows that there must be a second-best path.\n\nThe countryside consists of **R** bidirectional roads, each linking two of the **N** intersections, conveniently numbered from **1**to **N**. Robin starts at intersection **1**, and his friend is at intersection **N**.\n\nThe second-best path may share roads with any of the shortest paths, and it may backtrack i.e. use the same road or intersection more than once. The second-best path is the shortest path whose length is longer than the shortest path(s) (i.e. if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path)."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026#8804; 10)**, denoting the number of test cases.\n\nEach case contains two integers **N (1 \u0026#8804; N \u0026#8804; 5000)** and **R (1 \u0026#8804; R \u0026#8804; 10\u003csup\u003e5\u003c/sup\u003e)**. Each of the next **R** lines contains three space-separated integers: **u, v** and **w** that describe a road that connects intersections **u** and **v** and has length **w (1 \u0026#8804; w \u0026#8804; 5000)**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the second best shortest path as described above."}},{"title":"Sample","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\u003e2\n3 3\n1 2 100\n2 3 200\n1 3 50\n4 4\n1 2 100\n2 4 200\n2 3 250\n3 4 100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 150\nCase 2: 450\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}