{"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\"\u003eWayne是某个都市区域网络的管理员。他管理的网络可以形成一个简单连通图,其中有 $n$ 个顶点和 $m$ 条边,这意味着图中不包含自环,并且每两个顶点之间至少有一条路径且最多有一条边。此外,网络还满足每两个顶点之间最多有两条不相交的路径,它们之间没有共同的边。\u003cbr\u003e\u003cbr\u003eWayne知道网络中每条边的带宽,但这对他来说还不够。他需要大量的统计数据来展示,例如,他想知道每两个顶点之间的最大数据传输速率是多少。为了清晰起见,顶点从 $1$ 编号到 $n$,每条边每秒最大能传输的比特数也会给出。你的任务是帮助他计算以下公式的值:\u003cbr\u003e\u003cbr\u003e$$\\sum_{1 \\leq s \u0026lt; t \\leq n}{\\left(s \\oplus t \\oplus \\mathrm{flow}(s, t)\\right)},$$\u003cbr\u003e\u003cbr\u003e其中,$\\oplus$ 表示按位异或运算符,$\\mathrm{flow}(s, t)$ 表示顶点 $s$ 和顶点 $t$ 之间最大的每秒传输比特数。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行包含一个整数 $T$,表示测试用例的数量。\u003cbr\u003e接下来的行描述所有测试用例。对于每个测试用例:\u003cbr\u003e第一行包含两个整数 $n$ 和 $m$。\u003cbr\u003e接下来的 $m$ 行,每行包含三个整数 $u, v$ 和 $w$,表示顶点 $u$ 和顶点 $v$ 之间的双向边,每个方向最多可以传输 $w$ 比特每秒。\u003cbr\u003e$1 \\leq T \\leq 100$、$1 \\leq n \\leq 10^5$、$n - 1 \\leq m \\leq \\frac{3}{2}(n - 1)$、$1 \\leq u, v \\leq n$、$u \\neq v$、$0 \\leq w \u0026lt; 10^9$。\u003cbr\u003e保证所有测试用例中 $n$ 的总和不超过 $10^6$,标准输入文件的大小不超过 $26$ MiB。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,将答案输出在一行中。\u003cbr\u003e"}},{"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\u003e2\r\n3 3\r\n1 2 5\r\n2 3 6\r\n3 1 5\r\n5 6\r\n1 2 5\r\n2 3 6\r\n3 1 5\r\n3 4 6\r\n4 5 5\r\n5 3 6\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e27\r\n116\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"\u003cbr\u003e对于第一个样例,flow(1, 2) \u003d flow(1, 3) \u003d 10, flow(2, 3) \u003d 11。\u003cbr\u003e"}}]}