{"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就像那个节目一样,现在starvae也参加了一个节目,但它发生在A市和B市之间。Starvae在A市,女孩们在B市。每次starvae都可以到达B市并与他喜欢的女孩约会。但有两个问题,一个是starvae必须在最短的时间内到达B市,据说他必须走最短的路径。另一个问题是不能重复走同一条路。而starvae经过的城市可以重复经过。\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e所以,在一个好的RP下,starvae可能有很多机会去B市。但他不知道最多可以和喜欢的女孩约会多少次。你能帮助starvae吗?\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行是一个整数T,表示案例数量。(1≤T≤65)\u003cbr\u003e对于每个案例,第一行有两个整数n和m (2≤n≤1000, 0≤m≤100000),n是城市的数量,m是道路的数量。\u003cbr\u003e\u003cbr\u003e然后是m行,每行有三个整数a、b、c,(1≤a,b≤n,0≤c≤1000)表示从a到b有一条道路,距离为c,可能从b到a没有道路。可能从a到a有一条道路,但可以忽略。如果从a到b有两条道路,它们是不同的。\u003cbr\u003e\u003cbr\u003e最后一行是两个整数A和B(1≤A,B≤N,A!\u003dB),表示A市和B市的编号。\u003cbr\u003e每个案例之间可能有一些空行。"}},{"title":"输出","value":{"format":"HTML","content":"输出一行一个整数,表示starvae最多可以约会的次数。"}},{"title":"样例","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\u003e3\r\n7 8\r\n1 2 1\r\n1 3 1\r\n2 4 1\r\n3 4 1\r\n4 5 1\r\n4 6 1\r\n5 7 1\r\n6 7 1\r\n1 7\r\n\r\n6 7\r\n1 2 1\r\n2 3 1\r\n1 3 3\r\n3 4 1\r\n3 5 1\r\n4 6 1\r\n5 6 1\r\n1 6\r\n\r\n2 2\r\n1 2 1\r\n1 2 2\r\n1 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n1\r\n1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}