{"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\"\u003eNoticeļ¼Don\u0027t output extra spaces at the end of one line.\u003cbr\u003e\u003cbr\u003eKoishi loves flowers, especially Subterranean Roses.\u003cbr\u003e\u003cbr\u003eThe rose tree consists of $n$ nodes and $n-1$ branches. You can imagine the structure of the tree as an undirected tree. There are $m$ roses blossom, and Koishi wants to pick some of them. The $i$-th rose contains the node $u$ if and only if the distance from $u$ to $x_i$ is equal to or smaller than $r_i$. Additionally, the $i$-th flower\u0027s value is $v_i$.\u003cbr\u003e\u003cbr\u003eKoishi wants to maxmize the sum of values of picked roses. However, she doesn\u0027t like broken rose, so any two of her picked roses can\u0027t intersect. Two roses intersect if and only if there exists at least one node $u$ belongs to both of them. \u003cbr\u003e\u003cbr\u003eSo what\u0027s the largest sum of values of picked roses Koishi can get?\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains a positive integer $T(1\\leq T\\leq 500)$ representing the number of test cases.\u003cbr\u003e\u003cbr\u003eFor each test case, the first line contains two positive integers $n,m(1\\leq n,m\\leq 10^5)$, the number of nodes and roses.\u003cbr\u003e\u003cbr\u003eThe $i$-th line of the following $n-1$ lines contains two positive integers $u_i,v_i$,representing a branch in the tree which links node $u_i$ and $v_i$.\u003cbr\u003e\u003cbr\u003eThe $i$-th line of the following $m$ lines contains three non-negative integers $x_i,r_i,v_i(1\\leq x_i\\leq n,1\\leq r_i,v_i\\leq 10^9)$, describing the $i$-th rose.\u003cbr\u003e\u003cbr\u003eThere are at most $12$ test cases with $n+m\u0026gt;2000$"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, ouput one line with one non-negative integer as the largest sum of values."}},{"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\n10 5\r\n2 1\r\n3 1\r\n4 3\r\n5 3\r\n6 3\r\n7 1\r\n8 1\r\n9 7\r\n10 6\r\n2 3 1\r\n6 1 1\r\n9 5 1\r\n7 1 1\r\n1 9 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}