{"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":"\u003cdiv\u003e \n \u003cdiv\u003e\n 有一天雪菜和东马一起组队写代码,在连续WA了233次后,东马忍不住站起来大发雷霆,对雪菜说,\n \u003c/div\u003e \n \u003cdiv\u003e\n \u0026nbsp;\n \u003c/div\u003e \n \u003cdiv\u003e\n 明明是我先写的,A题也好,调试也好,可是为什么会这样呢,你为什么WA的这么熟练啊!连这种简单题怎么都不会做?\n \u003c/div\u003e \n \u003cdiv\u003e\n \u0026nbsp;\n \u003c/div\u003e \n \u003cdiv\u003e\n 我跟你讲,我可是身经百战了,哪个类型的题我没见过?你知道集训队的CerberuX菊苣吧,就是那个河老师,比你不知道高到哪里去啦,我和他谈笑风生啊!\n \u003c/div\u003e \n \u003cdiv\u003e\n \u0026nbsp;\n \u003c/div\u003e \n \u003cdiv\u003e\n 监考老师正巧就是CerberuX老师,他听到了东马的声音注意到了他们,准备走过去提醒他们比赛时不要站起来大声讲话。可是为了避免走动时影响其他同学,他准备找一条最短的路径过去。\n \u003c/div\u003e \n \u003cdiv\u003e\n \u0026nbsp;\n \u003c/div\u003e \n \u003cdiv\u003e\n 由于机房非常非常大,而且机器的布局也不规律,所以不同机位之间不一定有通路可以直接走过去,CerberuX一时半会找不出这样的一条路线,你能帮助他找到这条路并计算出需要多长时间才能走过去吗?\n \u003c/div\u003e \n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e输入包括多组数据。\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n \u0026nbsp;\n\u003c/div\u003e \n\u003cdiv\u003e\n 每组数据第一行是两个整数N、M(N\u0026lt;\u003d100,M\u0026lt;\u003d \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e10000),\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n \u0026nbsp;\n\u003c/div\u003e \n\u003cdiv\u003e\n N表示集训队机房内电脑数量,标号为1的是CerberuX的位置,标号为N的是东马和雪菜的位置,M则表示机房内有多少条路。\n\u003c/div\u003e \n\u003cdiv\u003e\n \u0026nbsp;\n\u003c/div\u003e \n\u003cdiv\u003e\n N \u003d M \u003d \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e0表示输入结束。\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n \u0026nbsp;\n\u003c/div\u003e \n\u003cdiv\u003e \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e接下来M行,每行包括3个整数A,B,C(1\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e \u0026lt;\u003d A,B \u0026lt;\u003d N,1 \u0026lt;\u003d C \u0026lt;\u003d \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e1000)\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e,表示在机位A与机位B之间有一条路,CerberuX需要C分钟的时间走过这条路。\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e 对于每组输入,输出一行,表示CerberuX从1号位置走到东马和雪菜位置的最短时间。如果CerberuX不能从1号位置走到东马和雪菜的位置,输出-10086。\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\n2 1\n1 2 3\n3 3\n1 2 5\n2 3 5\n3 1 2\n0 0\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\n3\n2\u003c/pre\u003e"}}]}