{"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\"\u003eYou have a directed weighted graph with $n$ vertexes and $m$ edges. The value of a path is the sum of the weight of the edges you passed. Note that you can pass any edge any times and every time you pass it you will gain the weight.\u003cbr\u003e\u003cbr\u003eNow there are $q$ queries that you need to answer. Each of the queries is about the k-th minimum value of all the paths.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input consists of multiple test cases, starting with an integer $t$ $(1\\leq t\\leq 100)$, denoting the number of the test cases.\u003cbr\u003eThe first line of each test case contains three positive integers n,m,q. $(1\\leq n,m,q\\leq 5*10^4)$\u003cbr\u003e\u003cbr\u003eEach of the next $m$ lines contains three integers $u_i,v_i,w_i$, indicating that the $i-th$ edge is from $u_i$ to $v_i$ and weighted $w_i$.$(1\\leq u_i,v_i \\leq n,1\\leq w_i\\leq 10^9)$\u003cbr\u003e\u003cbr\u003eEach of the next $q$ lines contains one integer $k$ as mentioned above.$(1\\leq k\\leq 5*10^4)$\u003cbr\u003e\u003cbr\u003eIt\u0027s guaranteed that $\\Sigma n$ ,$\\Sigma m$, $\\Sigma q , \\Sigma \\max(k)\\leq 2.5*10^5$ and $\\max(k)$ won\u0027t exceed the number of paths in the graph.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each query, print one integer indicates the answer in line."}},{"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\n2 2 2\r\n1 2 1\r\n2 1 2\r\n3\r\n4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003e1-\u0026gt;2 value :1\u003cbr\u003e\u003cbr\u003e2-\u0026gt;1 value: 2\u003cbr\u003e\u003cbr\u003e1-\u0026gt; 2-\u0026gt; 1 value: 3\u003cbr\u003e\u003cbr\u003e2-\u0026gt; 1-\u0026gt; 2 value: 3\u003cbr\u003e\u003cbr\u003e"}}]}