{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n The final battle is coming. Now Harry Potter is located at city 1, and Voldemort is located at city n. To make the world peace as soon as possible, Of course, Harry Potter will choose the shortest road between city 1 and city n. But unfortunately, Voldemort is so powerful that he can choose to destroy any one of the existing roads as he wish, but he can only destroy one. Now given the roads between cities, you are to give the shortest time that Harry Potter can reach city n and begin the battle in the worst case. \n \u003cbr\u003e \n\u003c/div\u003e\n\u003cbr\u003e给一个无向图,问任意删除一条边,求点 1 到点 n 的最短路径的最长长度,如果能使1不能到达n,输出-1."}},{"title":"Input","value":{"format":"HTML","content":"First line, case number t (t\u0026lt;\u003d20). \n\u003cbr\u003eThen for each case: an integer n (2\u0026lt;\u003dn\u0026lt;\u003d1000) means the number of city in the magical world, the cities are numbered from 1 to n. Then an integer m means the roads in the magical world, m (0\u0026lt; m \u0026lt;\u003d50000). Following m lines, each line with three integer u, v, w (u !\u003d v,1 \u0026lt;\u003du, v\u0026lt;\u003dn, 1\u0026lt;\u003dw \u0026lt;1000), separated by a single space. It means there is a bidirectional road between u and v with the cost of time w. There may be multiple roads between two cities. \n\u003cbr\u003e\n\u003cbr\u003e第一行 t 表示数据组数 \n\u003cbr\u003e对于每组测试数据 \n\u003cbr\u003en 表示点数,m 表示双向边数 \n\u003cbr\u003e接下来 m 行,u,v,w 表示 u 到 v 有一条边权为 w 的边\n\u003cbr\u003e2\u0026lt;\u003dn\u0026lt;\u003d1000,2\u0026lt;m\u0026lt;\u003d50000,1\u0026lt;\u003dw\u0026lt;1000"}},{"title":"Output","value":{"format":"HTML","content":"Each case per line: the shortest time to reach city n in the worst case. If it is impossible to reach city n in the worst case, output “-1”. \n\u003cbr\u003e\n\u003cbr\u003e对于每组测试数据输出最长长度,若无路径输出-1"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e3\n4\n4\n1 2 5\n2 4 10\n1 3 3\n3 4 8\n3\n2\n1 2 5\n2 3 10\n2\n2\n1 2 1\n1 2 2\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e15\n-1\n2\u003c/pre\u003e"}}]}