{"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":"几年后,杰瑞爱上了一个女孩,他经常走很长时间去看望她。但是,因为他和女朋友在一起的时间太多了,汤姆觉得被忽视了,想阻止他去看她。\n\n在对社区做了一些研究后,Tom发现社区由n栋房子组成,其中一些房子与有方向性的道路相连。为了去拜访他的女朋友,杰瑞需要从索引为1的房子开始,沿着最短的路径到索引为n的她家。\n\n现在汤姆想要封锁一些道路,这样杰瑞就得走更长的路才能到达他女朋友的家,他发现封锁一条路的成本等于它的长度。现在他想知道使Jerry走得更远的最小总成本。\n\n注意,如果Jerry一开始就不能到达他女朋友的家,那么答案显然是零。而且你不需要保证在堵住一些边缘后,仍然有一条路可以从杰瑞的家到他女朋友的家。"}},{"title":"Input","value":{"format":"HTML","content":"输入的第一行包含一个整数T(1≤T≤10),测试用例的数量。\n\n每个测试用例从一行开始,其中包含两个数字n,m(1≤n,m≤10000),即房屋的数量和附近的单行道的数量。\n\n接下来有M条线,每条线由三个整数x,y,c组成(1≤x,y≤n,1≤c≤109),表示存在一条从索引x到y的长度为c的单行道。"}},{"title":"Output","value":{"format":"HTML","content":"打印T行,每行包含一个整数,答案。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e1\n3 4\n1 2 1\n2 3 1\n1 3 2\n1 3 3\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e3\u003c/pre\u003e"}}]}