{"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":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n Jack likes to travel around the world, but he doesn’t like to wait. Now, he is traveling in the Undirected Kingdom. There are $n$ cities and $m$ bidirectional roads connecting the cities. Jack hates waiting too long on the bus, but he can rest at every city. Jack can only stand staying on the bus for a limited time and will go berserk after that. Assuming you know the time it takes to go from one city to another and that the time Jack can stand staying on a bus is $x$ minutes, how many pairs of city $(a, b)$ are there that Jack can travel from city $a$ to $b$ without going berserk? \n\u003c/div\u003e\n有n个城市,被m条无向边连接,每条边有一个时间,表示坐巴士从一个城市到另一城市需要等待的时间。\u003c/br\u003e\nJack最多等待巴士x分钟,也就是需要等待超过x分钟的巴士他就不会去坐,他在城市里可以得到休息,使得他恢复等待巴士的耐心。\u003c/br\u003e\n求有多少对城市(a,b), 他可以通过坐巴士的方式从a城市到达b城市。\u003c/br\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains one integer $T, T \\leq 5$, which represents the number of test case. \n\u003cbr\u003e \n\u003cbr\u003eFor each test case, the first line consists of three integers $n, m$ and $q$ where $n \\leq 20000, m \\leq 100000, q \\leq 5000$. The Undirected Kingdom has $n$ cities and $m$ bidirectional roads, and there are $q$ queries. \n\u003cbr\u003e \n\u003cbr\u003eEach of the following $m$ lines consists of three integers $a, b$ and $d$ where $a, b ∈ \\{1, . . . , n\\}$ and $d \\leq 100000$. It takes Jack $d$ minutes to travel from city $a$ to city $b$ and vice versa. \n\u003cbr\u003e \n\u003cbr\u003eThen $q$ lines follow. Each of them is a query consisting of an integer $x$ where $x$ is the time limit before Jack goes berserk. \n\u003cbr\u003e \n\u003cbr\u003e\n第一行一个整数T,表示测试数据组数。\u003c/br\u003e\n每组测试数据,第一行3个整数n,m和q。\u003c/br\u003e\n接下来m行,每行3个整数a,b,c.表示一条连接a和b的边,长度为c\u003c/br\u003e\n接下来q行,每行一个整数x\u003c/br\u003e\n\n\n\n"}},{"title":"Output","value":{"format":"HTML","content":"You should print $q$ lines for each test case. Each of them contains one integer as the number of pair of cities $(a, b)$ which Jack may travel from $a$ to $b$ within the time limit $x$. \n\u003cbr\u003e \n\u003cbr\u003eNote that $(a, b)$ and $(b, a)$ are counted as different pairs and $a$ and $b$ must be different cities.\u003c/br\u003e\n对于每个询问,输出有多少对(a,b) 满足a到b,可以不走超过x的边。\u003c/br\u003e\n(a,b)和(b,a)会是不同的方案。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e1\n5 5 3\n2 3 6334\n1 5 15724\n3 5 5705\n4 3 12382\n1 3 21726\n6000\n10000\n13000\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e2\n6\n12\u003c/pre\u003e"}}]}