题目内容

运维员要在一张通信网里完成一次闭环巡检。网中有 $p$ 个节点（编号 $1$ 到 $p$）和 $q$ 条链路，链路按输入顺序编号为 $1$ 到 $q$。第 $i$ 条链路连接节点 $x_i,y_i$，通行费用为 $c_i$。保证整张网连通；允许自环与重边。

运维员初始位于节点 $1$，可反复执行以下两类操作：

1. 实地巡检：沿一条连接当前节点与邻接节点 $y$ 的链路行走，完成对该链路的巡检并到达 $y$，花费恰为该链路费用。每条链路至少巡检一次。
2. 调度专线：从当前节点 $x$ 瞬移到任意其他节点 $z$（$z\neq x$）。可自选一条 $x$ 到 $z$ 的路径（允许重复经过节点与链路），专线票价等于该路径上编号最大的那条链路的费用。即若路径依次经过编号 $e_1,e_2,\dots,e_k$ 的链路，则票价为 $c_{\max\{e_1,\dots,e_k\}}$。

请计算：从节点 $1$ 出发，使全部链路都被实地巡检覆盖，最后返回节点 $1$ 时的最小总花费。

输入描述

第一行一个整数 $g$（$1\le g\le 10^4$），表示询问组数。

接下来共有 $g$ 组数据，每一组格式如下：

第一行两个整数 $p,q$（$1\le p\le 2\times 10^5$，$0\le q\le 2\times 10^5$）。

若 $q>0$，第二行 $q$ 个整数 $x_1,x_2,\dots,x_q$。

第三行 $q$ 个整数 $y_1,y_2,\dots,y_q$。

第四行 $q$ 个整数 $c_1,c_2,\dots,c_q$。

第 $i$ 条链路连接 $x_i$ 与 $y_i$，费用为 $c_i$（$1\le x_i,y_i\le p$，$1\le c_i\le 10^9$）。当 $q=0$ 时，上述三行省略。

保证每组图连通；所有组的 $p$ 之和与 $q$ 之和均不超过 $5\times 10^5$。

输出描述

输出一行，包含 $g$ 个整数，相邻整数之间用单个空格隔开。

第 $t$ 个数表示第 $t$ 组的最小总花费。

样例1

输入

4
1 0
1 2
1 1
1 1
5 3
2 1
1
2
7
4 4
1 2 3 1
2 3 4 1
10 10 10 1

输出

0 8 14 32

说明

• 第 $1$ 组：单点无边，答案 $0$。
• 第 $2$ 组：两条自环费用 $5、3$，实地走完即可，答案 $8$。
• 第 $3$ 组：巡检边花费 $7$，再乘调度专线返回，票价亦为 $7$，合计 $14$。
• 第 $4$ 组：四条边费用和为 $31$，再花 $1$ 返回，合计 $32$。