{"trustable":true,"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":"\u003cdiv class\u003d\"panel_content\"\u003eEvery year at the school competition, all the students who enter the finals will receive a very nice t-shirt. But every time our staff bring back hundreds of clothes from the store to the venue, they are very tired! So now they want to find the shortest route from the store to the venue, can you help them?\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Input consists of multiple test cases. For each test case, the first line contains two integers N and M (N\u0026lt;\u003d100, M\u0026lt;\u003d10000), where N represents the number of intersections on the main street of Chengdu, intersection 1 is the location of the store, and intersection N is the location of the venue. M represents the number of roads in Chengdu. The input ends when N\u003dM\u003d0. Then, there are M lines, each containing 3 integers A, B, C (1\u0026lt;\u003dA,B\u0026lt;\u003dN,1\u0026lt;\u003dC\u0026lt;\u003d1000), indicating that there is a road between intersection A and intersection B, and our staff need C minutes to walk this road. It is guaranteed that there is at least one route from the store to the venue.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output a line representing the shortest time for the staff to walk from the store to the venue."}},{"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 1\r\n1 2 3\r\n3 3\r\n1 2 5\r\n2 3 5\r\n3 1 2\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n2\r\n\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}