{"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\"\u003eYears later, Jerry fell in love with a girl, and he often walks for a long time to pay visits to her. But, because he spends too much time with his girlfriend, Tom feels neglected and wants to prevent him from visiting her.\u003cbr\u003eAfter doing some research on the neighbourhood, Tom found that the neighbourhood consists of exactly $n$ houses, and some of them are connected with directed road. To visit his girlfriend, Jerry needs to start from his house indexed $1$ and go along the shortest path to hers, indexed $n$. \u003cbr\u003eNow Tom wants to block some of the roads so that Jerry has to walk longer to reach his girl\u0027s home, and he found that the cost of blocking a road equals to its length. Now he wants to know the minimum total cost to make Jerry walk longer.\u003cbr\u003eNote, if Jerry can\u0027t reach his girl\u0027s house in the very beginning, the answer is obviously zero. And you don\u0027t need to guarantee that there still exists a way from Jerry\u0027s house to his girl\u0027s after blocking some edges.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input begins with a line containing one integer $T(1\\le T\\le 10)$, the number of test cases.\u003cbr\u003eEach test case starts with a line containing two numbers $n,m(1\\le n,m\\le 10000)$, the number of houses and the number of one-way roads in the neighbourhood.\u003cbr\u003e$m$ lines follow, each of which consists of three integers $x,y,c(1\\le x,y\\le n,1\\le c\\le 10^9)$, denoting that there exists a one-way road from the house indexed $x$ to $y$ of length $c$."}},{"title":"Output","value":{"format":"HTML","content":"Print $T$ lines, each line containing a integer, the answer."}},{"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\u003e1\r\n3 4\r\n1 2 1\r\n2 3 1\r\n1 3 2\r\n1 3 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}