{"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\"\u003eНа ежегодном школьном соревновании все участники, попавшие в финал, получают красивую футболку. Но когда наши сотрудники переносят сотни футболок из магазина на место соревнования, им очень тяжело! Поэтому сейчас им нужно найти самый короткий путь от магазина до места соревнования. Ты можешь помочь им?\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Ввод содержит несколько наборов данных. В каждом наборе данных первая строка содержит два целых числа N и M (N\u0026lt;\u003d100, M\u0026lt;\u003d10000). N обозначает количество перекрестков на главной улице Чэнду, перекресток с номером 1 - это место расположения магазина, перекресток с номером N - это место проведения соревнования, M обозначает количество дорог в Чэнду. N\u003dM\u003d0 обозначает конец ввода. Затем следуют M строк, каждая из которых содержит 3 целых числа A, B, C (1\u0026lt;\u003dA,B\u0026lt;\u003dN,1\u0026lt;\u003dC\u0026lt;\u003d1000), обозначающие, что между перекрестками A и B есть дорога, и наши сотрудники нуждаются во времени C минут, чтобы пройти этот путь.\u003cbr\u003eГарантируется, что существует по крайней мере один маршрут от магазина до места проведения соревнования.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"Для каждого ввода выведите одну строку, обозначающую минимальное время, за которое сотрудники достигнут места проведения соревнования от магазина."}},{"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"}}]}